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;
  }
}