首页 > 代码库 > [leetcode]Swap Nodes in Pairs

[leetcode]Swap Nodes in Pairs

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.

题中要求O(1)空间,且不允许修改list中节点的值。

事实上我尝试修改节点的值,还是过了,哈哈

算法思想:

每次选两个节点,同时需要维护第三个指针,就是这两个节点的前驱,以防链表断链。两节点互换很容易,换完之后要与前驱节点链接。

代码如下:

 1 public class Solution { 2     public ListNode swapPairs(ListNode head) { 3         if(head == null || head.next == null) return head; 4         ListNode hhead = new ListNode(0); 5         hhead.next = head; 6         ListNode one = head; 7         ListNode two = one.next; 8         ListNode pre = hhead; 9         while(one !=null && two != null){10             one.next = two.next;11             two.next = one;12             pre.next = two;13             pre = one;14             one = one.next;15             if(one == null) break;16             two = one.next;17         }18         return hhead.next;19     }20 }