Swap Two Nodes in Linked List

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.

Link

Lintcode_ladder

Method

1. x
2. x

Example

1. 1

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    /**
     * @param head a ListNode
     * @oaram v1 an integer
     * @param v2 an integer
     * @return a new head of singly-linked list
     */
    ListNode* swapNodes(ListNode* head, int v1, int v2) {
        // Write your code here
        if (!head) {
            return nullptr;
        }
        ListNode dummy(0);
        dummy.next = head;
        ListNode* cur = &dummy;
        ListNode* v1Prev = nullptr;
        ListNode* v2Prev = nullptr;
        // find
        while (cur->next) {
            if (v1Prev && v2Prev) {
                break;
            }
            if (cur->next->val == v1) {
                v1Prev = cur;
            }
            if (cur->next->val == v2) {
                v2Prev = cur;
            }
            cur = cur->next;
        }
        // swap
        if (!v1Prev || !v2Prev) {
            return dummy.next;
        }
        // make usre the seq is : v1 -> xxx -> v2
        if (v2Prev->next == v1Prev) {
            ListNode* tmp = v2Prev;
            v2Prev = v1Prev;
            v1Prev = tmp;
        }
        ListNode* v1ptr = v1Prev->next;
        ListNode* v2ptr = v2Prev->next;
        ListNode* v1next = v1ptr->next;
        // two nodes are adjacent
        if (v1ptr->next == v2ptr) {
            // first give the rest to next of v1
            v1ptr->next = v2ptr->next;
            // second, connect v2 to v1Prev->next
            v1Prev->next = v2ptr;
            // thid, connect v1 to v2ptr->next
            v2ptr->next = v1ptr;
        } else {
            // first give the rest to next of v1
            v1ptr->next = v2ptr->next;
            v2ptr->next = v1next;
            // second, connect v2 to v1Prev->next
            v1Prev->next = v2ptr;
            // thid, connect v1 to v2Prev->next
            v2Prev->next = v1ptr;
        }
        return dummy.next;
    }
};

Similar problems

x

Tags

x