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

[leetcode]Swap Nodes in Pairs

2024-07-12 22:15:14   229人阅读

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 }


联系
我们