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.

Have you met this question in a real interview?

Yes

Example

Given1->2->3->4->nulland v1 =2, v2 =4.

Return1->4->3->2->null.

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
        if (head == null) {
            return head;
        }

        ListNode dummy = new ListNode(0);
        dummy.next = head;

        ListNode preV1 = dummy;
        ListNode preV2 = dummy;
        ListNode prev = dummy;

        boolean findV1 = false;
        boolean findV2 = false;


        //1->2->3->4->5->6 v1 = 2, v2 = 4


        while (head != null) {
            if (head.val == v1) {
                preV1 = prev;
                findV1 = true;
            } else if (head.val == v2) {
                preV2 = prev;
                findV2 = true;
            }

            if (findV1 && findV2) {
                swap(preV1, preV2);
                return dummy.next;
            }

            prev = head;
            head = head.next;
        }

        return dummy.next;
    }

    //1->2->3->4->5->6 v1 = 2, v2 = 4
    //preV1 = 1
    //preV2 = 3
    //
    private void swap(ListNode preV1, ListNode preV2) {

        if (preV1.next != null && preV2.next != null){
            if (preV1.next.val == preV2.val) {
                ListNode currV1 = preV1.next;
                ListNode currV2 = preV2.next;
                ListNode v2Next = preV2.next.next;

                preV1.next = currV2;
                currV2.next = currV1;
                currV1.next = v2Next;
                return;
            } 

            if (preV2.next.val == preV1.val) {
                ListNode currV1 = preV1.next;
                ListNode currV2 = preV2.next;
                ListNode v1Next = preV1.next.next;

                preV2.next = currV1;
                currV1.next = currV2;
                currV2.next = v1Next;

                return;
            }

        }

        ListNode currV1 = preV1.next;
        ListNode v1Next = currV1.next;

        ListNode currV2 = preV2.next;
        ListNode v2Next = currV2.next;

        preV1.next = currV2;
        currV2.next = v1Next;

        preV2.next = currV1;
        currV1.next = v2Next;
    }
}