My accepted java code. used recursion.


  • 153
    W
    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;
        }
    }

  • 1
    E

    Is that constant space?


  • 9
    N

    No. the recursive stack uses O(n) space


  • 1
    Y

    This is really smart solution, though it is not constant space


  • 6
    X

    Very simple and clean, but not in constant space.

        if(head == null)
            return head;
            
        ListNode dummy = new ListNode(12);
        dummy.next = head;
        ListNode slow = head, fast = head.next,  prev = dummy;
        
        while(fast != null) {
            slow.next = fast.next;
            fast.next = slow;
            prev.next = fast;
            prev =slow;
            slow = slow.next;
            if(slow != null)
                fast = slow.next;
            else 
                break;
        } 
        
        return dummy.next;

  • 7

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

  • 0
    I

    @xuejingdong very smart and clean! Thanks. :)


  • 3
    L

    Ugh. Fuck this question, this is so elegant. Why must we use constant space.


  • 0
    S

    @xuejingdong Can I ask what is the difference between "return head" and "return dummy.next"?


  • 1
    N

    @shenhiboy A dummy node is often used in linked list questions in order to avoid a special case at the beginning of the list. In this case, without the dummy, the loop would start with prev set as null. This just saved him a null check.


  • 2

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

  • 1
    E

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


  • 0
    H

    @xuejingdong Hi, why your code is not in constant space. I think it is in constant space.


  • 0

    @huiyujie I guess that is because it makes use of recursion (which implicitly uses a stack for its operation). Hence it is not in constant space.


  • 0
    G
    This post is deleted!

  • 0
    T

    @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).

    True, but that's the case for any recursive implementation on a problem with a non-determinate end. By that logic, recursion should never be used on any linked list, trees, or any other structure where the recursive solution is the most likely the simplest and the most elegant - like we have here.

    No one here is writing production code to solve simple LeetCode problems. Recursion is fine.


  • 0
    S

    @zhugejunwei Hi! Can you please explain how the last if condition is used, why does it matter if the temp.next is set.


  • 0
    S

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

    I'm a newbie for programming and I've got a small problem:
    for the following code " if ((head == null)||(head.next == null)) " when i write as "list item if ( head == null || head.next == null) " there would be a time limit exceed error. Why it happens? Since I thought the "==" and "||" doesn't share the same priority.

    Anyone can help? Thanks a lot!


  • 0
    G

    @Stella_Wu "==" has higher priority than "||", so i don't think these two code had any difference,and I try the code you say, it work well.


  • 0
    S

    @GitOfDirector Thank you for your kind reply!
    But I tired the code once more and the error still occurs, could you please tell me why?
    0_1500106890274_d794d13d-44a3-4877-808f-f2cfb28e7355-image.png


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.