Swap Two Nodes in Linked List(lintcode 511)

Description

Given a linked list and two values v1 and v2. Swap the two nodes in the linked list with values v1 and v2. It's guaranteed there is no duplicate values in the linked list. If v1 or v2 does not exist in the given linked list, do nothing.

Notice:
You should swap the two nodes with values v1 and v2. Do not directly swap the values of the two nodes.

Example

Given 1->2->3->4->null and v1 = 2, v2 = 4.

Return 1->4->3->2->null.

Interface

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    /**
     * @param head a ListNode
     * @oaram v1 an integer
     * @param v2 an integer
     * @return a new head of singly-linked list
     */
    public ListNode swapNodes(ListNode head, int v1, int v2) {
        // Write your code here
    }
}

Idea

Notice that v1 is next to v2, v2 is next to v1, and v1 and v2 are non-adjacent are three different cases.

Solution

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    /**
     * @param head a ListNode
     * @oaram v1 an integer
     * @param v2 an integer
     * @return a new head of singly-linked list
     */
    public ListNode swapNodes(ListNode head, int v1, int v2) {
        // Write your code here
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode preV1 = dummy;
        ListNode preV2 = dummy;
        while (preV1.next != null) {
            if (preV1.next.val == v1) {
                break;
            }
            preV1 = preV1.next;
        }

        while (preV2.next != null) {
            if (preV2.next.val == v2) {
                break;
            }
            preV2 = preV2.next;
        }

        ListNode node1 = preV1.next;
        ListNode node2 = preV2.next;

        if (node1 == null || node2 == null) {
            return head;
        }

        if (preV1.next == preV2) {
            node1.next = node2.next;
            node2.next = node1;
            preV1.next = node2;
            return dummy.next;
        }

        if (preV2.next == preV1) {
            node2.next = node1.next;
            node1.next = node2;
            preV2.next = node1;
            return dummy.next;
        }

        ListNode postV2 = node2.next;
        preV1.next = node2;
        node2.next = node1.next;
        preV2.next = node1;
        node1.next = postV2;

        return dummy.next;
    }
}