Swap Nodes in Pairs

Leave a comment

June 3, 2016 by oneOokay

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.


这里要注意一个memory limit exceeded。尽量少用新的ListNode。

注意只剩最后一个单数的node的时候,我们可以什么都不做,所以while loop的时候可以对next和next.next进行判定

Iterative:
public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(0);//head会变,引入dummy
dummy.next = head;
//因为已经有dummy来指向head了,所以这里就把head用作指针
进行遍历,节省了一个指针的空间
head = dummy;
while(head.next != null && head.next.next != null){
ListNode n1 = head.next;
ListNode n2 = head.next.next;
head.next = n2;
n1.next = n2.next;//这里节省了另外一个next指针
n2.next = n1;
head = n1;
}
return dummy.next;
}
Recursive:
  public ListNode swapPairs(ListNode head) {
 if (head == null || head.next == null)
 return head;
 
 ListNode second = head.next;
 ListNode third = second.next;
 second.next = head;
 head.next = swapPairs(third);
 return second;
 }
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: