LC024-兩兩交換連結清單中的節點

24. 兩兩交換連結清單中的節點

難度中等741

給定一個連結清單，兩兩交換其中相鄰的節點，并傳回交換後的連結清單。

你不能隻是單純的改變節點内部的值，而是需要實際的進行節點交換。

示例 1：

輸入：head = [1,2,3,4]
輸出：[2,1,4,3]      

示例 2：

輸入：head = []
輸出：[]      

棧:

利用棧的特性不斷地進行疊代,每次給棧中放入間隔元素就有棧中取出,

借助棧的特性,放進去的1,2 拿出的是2 1

在把其串聯起立,就是所求的結果

public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
//利用棧的特殊性
        Stack<ListNode> stack = new Stack<>();
        ListNode p = new ListNode(0);//新連結清單的結點
        //設定一個輔助變量temp 進行周遊
        ListNode temp = head;
        //head指向新的p節點，函數結束時傳回head.next即可
        head = p;
        while (temp != null && temp.next != null) {
            //放入兩個結點到棧中
            stack.push(temp);
            stack.push(temp.next);
            //目前節點往前走兩步
            temp=temp.next.next;
            p.next=stack.pop();
            //p結點往下也走兩步
            p=p.next;
            p.next=stack.pop();
            p=p.next;
        }
        //注意邊界條件，當連結清單長度是奇數時，cur就不為空
        if(temp!=null) {
            p.next = temp;
        } else {
            p.next = null;
        }
        return head.next;
    }      

疊代實作

疊代需要 三個指針 a b temp

例如連結清單

• 第一次疊代的時候: a= 1 b =2
• 通過a.next = b,next b.next=a 反轉過來. 也就是1 2 變稱 2 1
• 當數組變成 2 1 和 4 3時候,這時候需要 1 4 穿起來,這時候就需要第三個指針temp
• tmp指針用來處理邊界條件的
• 現在連結清單就變成2->1->3->4

• temp和b都指向1節點，等下次疊代的時候

  a就變成3，b就變成4，然後tmp就指向b，也就是1指向4

temp.next = b;
a.next = b.next;
b.next = a;
temp = a;      

class Solution {
  public ListNode swapPairs(ListNode head) {
    //增加一個特殊節點友善處理
    ListNode p = new ListNode(-1);
    p.next = head;
    //建立a，b兩個指針，這裡還需要一個tmp指針
    ListNode a = p;
    ListNode b = p;
    ListNode temp = p;
    while(b!=null && b.next!=null && b.next.next!=null) {
      //a前進一位，b前進兩位
      a = a.next;
      b = b.next.next;
      //進行換位
            //頭結點指向2
      temp.next = b;
          //通過a.next = b,next   b.next=a  反轉過來.  也就是1 2  變稱 2 1
      a.next = b.next;
      b.next = a;
       //tmp和b都指向1節點，等下次疊代的時候
      //a就變成3，b就變成4，然後tmp就指向b，也就是1指向4
      temp = a;
      b = a;
    }
    return p.next;
  }
}      

遞歸解法

class Solution {
  public ListNode swapPairs(ListNode head) {
    //遞歸的終止條件
    if(head==null || head.next==null) {
      return head;
    }
    //假設連結清單是 1->2->3->4
    //這句就先儲存節點2
    ListNode tmp = head.next;
    //繼續遞歸，處理節點3->4
    //當遞歸結束傳回後，就變成了4->3
    //于是head節點就指向了4，變成1->4->3
    head.next = swapPairs(tmp.next);
    //将2節點指向1
    tmp.next = head;
    return tmp;
  }
}