前言
對單鏈表還不熟悉的朋友，可以參考這篇文章順序表 和 鏈表 - 單向鏈表部分
題目
這個題目不好講，我直接將代碼 和 決議圖 給你們，需要你們自己多琢磨，當然一些重要代碼部分我會注釋一下！
?
遞回解法
class Solution {
public ListNode swapPairs(ListNode head) {
if(head == null || head.next== null){
return head;
}
ListNode newHead = head.next;
head.next = swapPairs(newHead.next);
newHead.next = head;
return newHead;
}
}
代碼決議圖
?
迭代
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode newHead = new ListNode();
newHead.next = head;
ListNode tmp = newHead;
while(tmp.next!=null && tmp.next.next!=null){
ListNode node1 = tmp.next;
ListNode node2 = tmp.next.next;
tmp.next = node2;
node1.next = node2.next;
node2.next = node1;
tmp = node1;
}
return newHead.next;
}
}
代碼決議
還有一種方法 ，是通過 “堆疊的特性：先入后出，后進先出” 來實作了的
?
代碼
class Solution {
public ListNode swapPairs(ListNode head) {
if(head == null || head.next == null){
return head;
}
Stack<ListNode> stack = new Stack<>();// 創建 堆疊
ListNode p = new ListNode();// 新建一個節點
ListNode cur = head;// 創建 一個 head頭節點替身，去遍歷陣列
head = p;// 將 head 重新指向 一個 節點，也就是說上面cur成為了真正的頭節點
while(cur!=null && cur.next!=null){
stack.add(cur);// 入堆疊
stack.add(cur.next);// 入堆疊
cur = cur.next.next;// 舊鏈表的頭節點 向后移動2位，舊鏈表的頭節點不重要，丟了就丟了
p.next = stack.pop();// 出堆疊， 將舊鏈表的兩個節點"交換"后，原先的第二個節點取出，
p = p.next; //將其接入 新鏈表當中
p.next = stack.pop();// 出堆疊， 將 舊鏈表的兩個節點"交換"后，原先的第一個節點取出，
p= p.next;//將其接入 新鏈表當中
}
if(cur!=null){// 節點為奇數的情況，那么需要將最后一個節點，接入新鏈表中
p.next = cur;
}else{// 節點為偶數的情況，那么需要將最后一個節點的next 置為 null
p.next = null;
}
return head.next;// 最后回傳 頭節點的next
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/386578.html
標籤：其他
上一篇：DETR代碼復現