关于java:链表反转全家桶二动画详解两两交换链表中的节点

45次阅读

共计 1615 个字符，预计需要花费 5 分钟才能阅读完成。

上回说到面试中的一个高频题目：单链表反转，提到它的“难兄难弟”不是那么简略。明天就来剖析一下它的二哥：“两两替换链表中的节点”。

题目形容如下。

给定一个链表，两两替换其中相邻的节点，并返回替换后的链表。

你不能只是单纯的扭转节点外部的值，而是须要理论的进行节点替换。

示例:
给定 1->2->3->4, 你应该返回 2->1->4->3.

办法一：三指针迭代
有了上回单链表反转的双指针迭代法的根底，再来解决它二哥，就绝对容易很多了。
“巧妇难为无米之炊”。题目中说的是要两两替换，那首先得有两个节点才行，所以上来先判断够两个节点才持续替换，而且循环持续的条件也是要满足剩下的节点够两个才行。
咱们能够应用两个变量 first 和second来示意以后要进行替换的第一个节点和第二个节点。

如上图，替换后，2nd节点指向 1st 节点，而 1st 节点不能再指向 2nd 节点了，否则就造成了环。应该让 1st 节点指向 2nd 节点原来的下一个节点，所以咱们须要当时把 2nd 节点原来的下一节点记录下来。
替换操作伪代码如下：

ListNode third = second.next;
second.next = first;
first.next = third;

同时，要思考上面的这种场景，节点 1 和节点 2 曾经实现替换，当初轮到节点 3 和节点 4 的替换，要保障节点 3 和节点 4 替换后，节点 1 指向的是节点 4，所以还要记录每一轮替换的前驱节点，下图这个例子外面前驱节点就是节点 1。

最初要返回的头指针为第一轮替换中的第二个节点。
动画演示如下。

class Solution {public ListNode swapPairs(ListNode head) {if (head == null || head.next == null) {return head;} 
        ListNode pre = null, first = head, second = head.next;
        ListNode ans = second;

        while (first != null && second != null) {
            ListNode third = second.next;
            second.next = first;
            first.next = third;
            // 记录前驱节点
            if (pre != null) {pre.next = second;}
            pre = first;
            // 1st，2nd 向前走
            first = third;
            second = (first != null) ? first.next : null;
        }
        return ans;
    }
}

复杂度剖析

工夫复杂度：O(n)。
空间复杂度：O(1)。

办法二：递归
上回说到的递归的时候，我写了一段本人都递归的感悟，这里忍不住再写一遍。

递归是个神奇的存在，那么简略，又那么简单，有时感觉它很近，实际上它却那么远，有时感觉重新认识了它，可它还是那个它，从未扭转过。每一次应用递归，都会对它了解更深一点。

如果把替换两个节点看做一个回合的话，那么两两替换链表中的所有节点是由很多这样的回合组成。递归是要倒着来的，就是说咱们在进行以后回合的替换的时候，能够假设未来的回合曾经实现了。
如下示意图所示，还拿链表 1->2->3->4->5->null 来举例，在进行节点 1 和节点 2 的替换的时候，假设 3->4->5->null 曾经实现了替换，节点 1 指向 swapPairs(3) 返回的节点：

代码如下：

class Solution {public ListNode swapPairs(ListNode head) {if (head == null || head.next == null) {return head;} 
        ListNode first = head, second = head.next;
        first.next = swapPairs(second.next);
        second.next = first;

        return second;
    }
}

复杂度剖析