首页 > 代码库 > Swap Nodes in Pairs leetcode java
Swap Nodes in Pairs leetcode java
题目:
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
.http://i.cnblogs.com/EditPosts.aspx?opt=1
Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.
题解:
这道题考察了基本的链表操作,注意当改变指针连接时,要用一个临时指针指向原来的next值,否则链表丢链,无法找到下一个值。
本题的解题方法是:
需要运用fakehead来指向原指针头,防止丢链,用两个指针,ptr1始终指向需要交换的pair的前面一个node,ptr2始终指向需要交换的pair的第一个node。
然后就是进行链表交换。
需要用一个临时指针nextstart, 指向下一个需要交换的pair的第一个node,保证下一次交换的正确进行。
然后就进行正常的链表交换,和指针挪动就好。
当链表长度为奇数时,ptr2.next可能为null;
当链表长度为偶数时,ptr2可能为null。
所以把这两个情况作为终止条件,在while判断就好,最后返回fakehead.next。
代码如下:
2 if(head == null || head.next == null)
3 return head;
4
5 ListNode fakehead = new ListNode(-1);
6 fakehead.next = head;
7
8 ListNode ptr1 = fakehead;
9 ListNode ptr2 = head;
10
11 while(ptr2!=null && ptr2.next!=null){
12 ListNode nextstart = ptr2.next.next;
13 ptr2.next.next = ptr2;
14 ptr1.next = ptr2.next;
15 ptr2.next = nextstart;
16 ptr1 = ptr2;
17 ptr2 = ptr2.next;
18 }
19 return fakehead.next;
20 }
Reference://http://gongxuns.blogspot.com/2012/12/leetcodeswap-nodes-in-pairs.html