全ての記事

leetcode war 24 - swap nodes in pairs

2017-10-23 @sunderls

leetCode js

https://leetcode.com/problems/swap-nodes-in-pairs/description/

Given a linked list, swap every two adjacent nodes and return its head. For example, Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

analysis

it seems we can use three cursors: p1, p2, p3

p1: head, p2: 1, p3:2

swap
p1.next = p3
p3.next = p2
p2.next = p3.next
p1 = p2
p2 = p2.next
p3 = p2.next.next

should stop when p3 or p2 are unable to assign a new node

trial

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var swapPairs = function(head) {

    var start = new ListNode(null);
    start.next = head;

    var p1 = start;
    var p2;

    // continues if p1 exist
    while (p1) {
        p2 = p1.next;

        if (!p2 || !p2.next) {
            break;    
        }

        p3 = p2.next;

        p1.next = p3;
        p2.next = p3.next;
        p3.next = p2;

        p1 = p2;
    }

    return start.next
};

this passed, but ranks only bottom 40%. oh