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进行判定

public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(0);//head会变,引入dummy
dummy.next = 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;
  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;

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: