all articles

leetcode war 24 - swap nodes in pairs

2017-10-23

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);

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 