@@ -0,0 +1,2111 @@
+package lintcode.list;%0A%0Aimport fundamentals.list.ListNode;%0A%0A/**%0A */%0Apublic class Solution %7B%0A%0A    // 511-Swap Two Nodes in Linked List%0A    // Note many edge cases: v1 or v2 not found; v2 is before v1; v1 is predecessor of v2; v1 is head%0A    public ListNode swapNodes(ListNode head, int v1, int v2) %7B%0A        ListNode dmy = new ListNode(0);%0A        dmy.next = head;%0A        for (ListNode n = dmy, p1 = null; n.next != null; n = n.next) %7B%0A            if (n.next.val == v1 %7C%7C n.next.val == v2) %7B%0A                if (p1 == null) %7B%0A                    p1 = n;%0A                %7D else %7B%0A                    ListNode p2 = n, n1 = p1.next, n2 = p2.next, suc1 = n1.next;%0A                    p1.next = n2;%0A                    if (n1 == p2) %7B%0A                        n1.next = n2.next;%0A                        n2.next = n1;%0A                    %7D else %7B%0A                        p2.next = n1;%0A                        n1.next = n2.next;%0A                        n2.next = suc1;%0A                    %7D%0A                    return dmy.next;%0A                %7D%0A            %7D%0A        %7D%0A        return head;%0A    %7D%0A%0A    public ListNode swapNodes_my(ListNode head, int v1, int v2) %7B%0A        ListNode dmy = new ListNode(0), pre1 = null, pre2 = null;%0A        dmy.next = head;%0A        for (ListNode n = dmy; n.next != null; n = n.next) %7B%0A            if (n.next.val == v1) %7B%0A                pre1 = n;%0A            %7D else if (n.next.val == v2) %7B%0A                pre2 = n;%0A            %7D%0A        %7D%0A%0A        // If cannot find both, do nothing!%0A        if (pre1 == null %7C%7C pre2 == null) %7B%0A            return head;%0A        %7D%0A%0A        // Note edge case that n1 and n2 is neighbor%0A        ListNode n1 = pre1.next, suc1 = n1.next, n2 = pre2.next;%0A        if (n1 == pre2) %7B%0A            pre1.next = n2;%0A            n1.next = n2.next;%0A            n2.next = n1;%0A        %7D else if (n2 == pre1) %7B%0A            pre2.next = n1;%0A            n2.next = n1.next;%0A            n1.next = n2;%0A        %7D else %7B%0A            pre1.next = n2;%0A            pre2.next = n1;%0A            n1.next = n2.next;%0A            n2.next = suc1;%0A        %7D%0A        return dmy.next;%0A    %7D%0A%0A%7D%0A

swap two nodes in list