迭代

其实就是以两个为一组,交换结点的指针指向。
如何交换两个结点?
以 ...->A->B->C->...为例:
要交换B、C结点,只需要让A与C相连,B插入C与后续链表中。更具体的步骤如下:

  1. 保存C结点。
  2. 把B结点的next指向C后面的链表。
    ...->A      C->...
           ↘ B↗
  3. C的next指向B。
    ...->A ↘         ...
               C-> B↗
  4. 最后把A的next指向C。
    ...->A->C       ...
                  ↘ B↗

懂得了如何转换,那只要套个循环,在每两个结点的做同样的操作即可把整条链表都进行结点的交换了。

class Solution {
    public ListNode swapPairs(ListNode head) { 
        // 设置头结点便于操作
        ListNode sentinel = new ListNode(0);
        sentinel.next = head;
        ListNode cur = head, pre = sentinel;
        // 注释模拟一次循环的过程
        // 以...->A->B->C->...为例,要交换的结点为B、C
        // pre指向A,cur指向B
        while(cur != null && cur.next != null){
            // 保存下一个结点,即例子中的C
            ListNode nextNode = cur.next;
            // 让B指向C后面的链表
            cur.next = nextNode.next;
            // 让C指向B,完成B、C的交换,但此时C没有结点指向它
            nextNode.next = cur;
            // pre指向连接回C,
            pre.next = nextNode;
            // 修改pre和cur指向,准备下一次遍历
            pre = cur;
            cur = cur.next;
        }
        return sentinel.next;
    }
}