算法数据结构---两两交换链表节点

本篇主要是在学习链表数据结构中时，进行两两交换链表元素时所一步一步执行的操作.

题目来源于力扣24. 两两交换链表中的节点。

此类题我们通常采取虚拟头节点的方式来简化我们的链表元素交换后的指向，假设有这样一个单链表如下,其头节点为head：

首先我们要先定义一个虚拟头节点dummyhead指向头节点head. 接下来开始进行交换，现在我们的链表元素个数共5个，此处我们两两交换的1-2换，3-4换，而由于值为5的节点指向了null，故其不用再做交换；

事实上，当链表元素个数为奇数时，最后一个元素就不用再交换了；当链表元素个数为偶数时，恰好完成成对的交换。

之后我们便开始进行交换，此时需要明确两点:

(1)current指针如何定义？

(2)链表终止交换的条件?

首先我们回答问题(1)，按照链表的结构，如果想交换1-2，那么必然要找到值为1、值为2的前一个节点，值为2的前一个节点就是值为1的节点，那么值为1的前一个节点是谁呢？显然就是我们先前定义好的虚拟头节点dummyhead,故我们初始化将current指针指向dummyhead节点：

对于问题(2)，当链表元素个数为偶数个时，根据cur指针的定义，仅当
cur.next.next不为null时，链表才进行交换元素；当链表元素个数为奇数个时，如此例当中，当交换完3-4后，cur指针指向值为5的前一个节点，此时cur.next不为null；故而我们的循环进行的条件是cur.next !=null && cur.next.next!=null

此处两个条件不能调换顺序，由于短路运算符的原因，一旦交换条件的顺序，假设cur.next=null,那么由于首先判断的条件为cur.next.next!=null，会直接报空指针异常，后面的条件也不再会进行判断；所以必须要把cur.next!=null这个条件放在第一个，意为仅当cur.next！=null时才会执行后面的cur.next.next!=null的判断。

回答完这两个问题之后，便可以进行元素的交换了：

每次循环，交换的步骤都分为3步:
(1)cur.next -> cur.next.next
(2)cur.next.next -> temp1
(3)temp1 -> temp2

之后我们便可以编写代码逻辑了:(基于Java，依次采用多次迭代的方法和递归的方法实现了相应需求)

首先定义好单链表：

 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
1
2
3
4
5
6
7

采用迭代法实现:

//迭代法
class Solution {
    public ListNode swapPairs(ListNode head) {
        //传入一个头节点，返回两两swap节点后的链表

        //初始化一个虚拟头节点dummyhead，指针指向头节点head
        ListNode dummyhead=new ListNode(-1);
        ListNode cur=dummyhead;
        dummyhead.next=head;
        ListNode temp1;//临时节点，保存两个节点之中的第一个节点
        ListNode temp2;//临时节点，保存两个节点之中的第二个节点
        ListNode temp;// 临时节点，保存两个节点后面的节点

        //循环判断条件
        //此处短路与一定不能把条件前后调换，否则可能空指针异常
        while(cur.next!=null && cur.next.next!=null){
            //先分别定义两个临时指针temp1,temp2
            temp1=cur.next;
            temp=cur.next.next;
            temp2=cur.next.next.next;

            //开始3步换序
            cur.next=temp;
            temp.next=temp1;
            temp1.next=temp2;
            cur=temp1;
        }
        //返回虚头节点的下一节点
        return dummyhead.next;
    }   
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

采用递归法实现能更加简化:

// 递归法
class Solution {
    public ListNode swapPairs(ListNode head) {
        // base case 退出提交
        if(head == null || head.next == null) return head;
        // 获取当前节点的下一个节点
        ListNode next = head.next;
        // 进行递归
        ListNode newNode = swapPairs(next.next);
        // 这里进行交换
        next.next = head;
        head.next = newNode;

        return next;
    }
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16