SwapNodesInPairs [source code]

public class SwapNodesInPairs {
static
/******************************************************************************/
class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode (0), slow = head;
        if (slow == null || slow.next == null)
            return head;
        ListNode fast = slow.next, slow_prev = dummy;
        dummy.next = head;
        while (true) {
            ListNode next = fast.next;
            slow_prev.next = fast;
            slow.next = next;
            fast.next = slow;
            // advance
            slow_prev = slow;
            if ((slow = slow.next) == null)
                break;
            if ((fast = slow.next) == null)
                break;
        }
        return dummy.next;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        SwapNodesInPairs.Solution tester = new SwapNodesInPairs.Solution();
        int[][] inputs = {
            {1, 2}, {2, 1},
            {1,2,3,4}, {2,1,4,3},
        };
        for (int i = 0; i < inputs.length / 2; i++) {
            ListNode head = ListNode.buildListNode (inputs[2 * i]);
            String head_str = ListNode.serialize (head);
            String ans_str = ListNode.serialize (ListNode.buildListNode (inputs[2 * i + 1]));
            System.out.println (Printer.separator ());
            ListNode output = tester.swapPairs (head);
            String output_str = ListNode.serialize (output);
            System.out.printf ("%s -> %s, expected: %s\n", 
                head_str, Printer.wrapColor (output_str, output_str.equals (ans_str) ? "green" : "red"), ans_str
            );
        }
    }
}

感觉又是一个脑筋急转弯的题目, 看给的这些限制就知道了, 想想办法;

最后还是一个有惊无险的AC了, 速度是4ms (62%). 这种题目, 最最重要的一点, 始终就是要多画图多笔算, 这个强调很多遍了;

一个小的细节是, 这题最好是第一次swap完成之后再advance; 因为我一开始初始化的时候, 两个指针是先初始化到实际的node上面的; 当然, 另外一个思路是可以用两个dummy head, 把slow和fast都先摆在上面, 这样循环里面就可以先advance然后再swap, 不过没有什么特殊的意义这样做, 现在这么写也挺好的;

意识到需要保存prev这个应该不难了; 最后advance的逻辑实际上就是自己画个图就知道了; 盯着代码看估计看的很乱; 另外这题本身确实不算难, 尤其是advance和cache prev之间的处理关系并不复杂;

看discussion的时候意识到我这里这个只要保证第一个iteration是先swap再advance, 那么实际上是不需要dummy的; 不过养成一个好习惯没坏处好吧;

这一题其实还是一个快慢指针的技巧, 而且跟之前一个delete Nth from end很像, 维护的是两个固定间距的指针而不是倍速. 注意这里的另外一个限制, 不允许你修改任何node本身的val, 实际上, 这种通过改val来投机取巧的做法在LinkedList题目当中还真不算少见; 之前那个题目就看到Stefan用过一次;

没有dummy的版本:

class Solution {  
    public ListNode swapPairs(ListNode head) {  
        ListNode slow = head;  
        if (slow == null || slow.next == null)  
            return head;  
        ListNode fast = slow.next, slow_prev = null, res = fast;  
        while (true) {  
            ListNode next = fast.next;  
            if (slow_prev != null)  
                slow_prev.next = fast;  
            slow.next = next;  
            fast.next = slow;  
            // advance  
            slow_prev = slow;  
            if ((slow = slow.next) == null)  
                break;  
            if ((fast = slow.next) == null)  
                break;  
        }  
        return res;  
    }  
}

没有editorial;

首先, 如果你仔细读了题目, 就注意到这里的空间限制非常的扎眼, 而我们以前说过, 一个规避空间限制的旁门左道就是recursion; 但是这个其实也是有一定风险的, 具体还是看实际面试的时候面试官是否允许, 因为Stack严格来说也是一个space占用;

@whoji said in My accepted java code. used recursion.:

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

这种recursion算法实际上设计起来并不简单; 但是掌握方法还是可以做的; 这种LinkedList的recursion, 一般都是标准的peel head recursion, 所以一般你确定你一个iteration的head到底是多少, 就不难处理了; 这里很明显, 一个head应该是两个node的一个pair; 然后你assume你后面返回上来的是一个正确的head for the rest of the list, 那么你当前iteration做什么? 想好就行了;

这种算法的设计, 一开始的一个难点是往往忘记了你的recursion函数是有返回值的, 而且往往返回的就是一个node. 把这个记清楚, 其他的设计往往就不是特别难了;

@navari said in My accepted java code. used recursion.:

No. the recursive stack uses O(n) space

一个不依赖prev指针的做法:

@zhugejunwei said in My accepted java code. used recursion.:

Iteration version:

public class Solution {  
    public ListNode swapPairs(ListNode head) {  
        if (head == null || head.next == null) return head;  
        ListNode cur = head;  
        ListNode newHead = head.next;  
        while (cur != null && cur.next != null) {  
            ListNode tmp = cur;  
            cur = cur.next;  
            tmp.next = cur.next;  
            cur.next = tmp;  
            cur = tmp.next;  
            if (cur != null && cur.next != null) tmp.next = cur.next;  
        }  
        return newHead;  
    }  
}

刚开始没看懂, again,还是要画图; 首先, 他意识到一个问题, 我们反正是两个两个的操作, 所以实际上不需要维护两个指针, 直接一个指针就行了; 因为LinkedList的性质, 所以我们肯定维护slow比较方便(你在fast的时候, 你是无法通过fast来access slow的); 另外一个insight就是, 虽然我们走到下一个pair的时候, 无法access之前的pair了, 但是这不代表我们无法维护两个pair之间的关系: every iteration is the prev of next iteration. 所以你只要在当前的pair, 提前在下一个pair找到合理的衔接位置就行了; 总体来说这个算法还是有点思路的;

对于recursion的另外一个理智批评:

@EDGE1777 said in My accepted java code. used recursion.:

@lekzeey unless compiler is geared towards tail recursion, this will cause stack overflow if the list is large enough (due to the function calls).

@cdai said in My accepted java code. used recursion.:

Very nice! Never thought that recursion could help save dmy, pre and tmp. The comparison is much clear as the followings. Thanks for sharing!

    // pre->cur->suc->tmp ==> pre->suc->cur->tmp ==> pre->suc->cur(pre)->tmp  
    public ListNode swapPairs(ListNode head) {  
        ListNode dmy = new ListNode(0), pre = dmy;  
        dmy.next = head;  
        while (pre.next != null && pre.next.next != null) {  
            ListNode cur = pre.next, suc = cur.next, tmp = suc.next;  
            pre.next = suc;  
            suc.next = cur;  
            cur.next = tmp;  
            pre = cur;  
        }  
        return dmy.next;  
    }  

    // O(N) time and space due to recursion  
    public ListNode swapPairs(ListNode cur) {  
        if (cur == null || cur.next == null) return cur;  
        ListNode suc = cur.next;  
        cur.next = swapPairs(suc.next);  
        suc.next = cur;  
        return suc;  
    }

@tusizi said in My simple JAVA solution for share:

    public ListNode swapPairs(ListNode head) {  
        ListNode dummy = new ListNode(0);  
        dummy.next = head;  
        ListNode current = dummy;  
        while (current.next != null && current.next.next != null) {  
            ListNode first = current.next;  
            ListNode second = current.next.next;  
            first.next = second.next;  
            current.next = second;  
            current.next.next = first;  
            current = current.next.next;  
        }  
        return dummy.next;  
    }

LinkedList类的题目思路还是很多的;

跟我的做法非常像的一个版本:

@YuTingLiu said in My straight-forward Java solution without recursion or dummy nodes (0ms):

• The idea is straightforward: use two pointers and swap
  • a.next = b.next, b.next = a.
  • Then continue the next pair, b = a.next.next, a=a.next
  • Remember to check null
  • Remember to track new head
  • Remember to link the new pair after the prior nodes.

Attached is the accepted code.

public class Solution {  
  public ListNode swapPairs(ListNode head) {  
    if(head==null || head.next==null) return head;  
    ListNode newHead = head.next, a=head,b=a.next,pre = null;  
    while(a!=null && b!=null){  
      a.next = b.next;  
      b.next = a;  
      if(pre!=null) pre.next = b;  
      if(a.next==null) break;  
      b = a.next.next;  
      pre = a;  
      a = a.next;  
    }  
    return newHead;  
  }  
}

• AC, 0ms

区别无非在于我的方法比他的更加依赖break一点, 无所谓了, 过了就行了;

submission基本波动, recursion稍微快一点;

Problem Description

Given a linked list, swap every two adjacent nodes and return its head.

For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

Difficulty:Medium
Total Accepted:199.2K
Total Submissions:511.5K
Contributor:LeetCode
Companies
microsoftbloomberguber
Related Topics
linked list
Similar Questions
Reverse Nodes in k-Group