首页 > 代码库 > Swap Nodes in Pairs

Swap Nodes in Pairs

Link: http://oj.leetcode.com/problems/swap-nodes-in-pairs/

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.

 

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     int val;
 5  *     ListNode next;
 6  *     ListNode(int x) {
 7  *         val = x;
 8  *         next = null;
 9  *     }
10  * }
11  */
12 public class Solution {
13     public ListNode swapPairs(ListNode head) {
14         if (head == null || head.next == null)
15             return head;
16         ListNode pre = new ListNode(0);
17         pre.next = head;
18         head = pre;
19         ListNode cur = pre.next, post = cur.next;
20         while (post != null) {
21             ListNode temp = post.next;
22             post.next = cur;
23             cur.next = temp;
24             pre.next = post;
25             pre = cur;
26             cur = temp;
27             post = temp;
28             if (cur != null)
29                 post = cur.next;
30         }
31         return head.next;
32     }
33 }

For the basic idea, please refer to http://www.cnblogs.com/Altaszzz/p/3704780.html