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.
Naive Way:如果要交换两个指针,必须要知道他们的父指针而非本身。可以使用两个指针,一个每回跳两次,一个每回跳一次,交换他们的子节点。
使用constant space。并且使用了一个额外的头结点方便记录返回值。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode swapPairs(ListNode head) {
ListNode newHead = new ListNode(0);
newHead.next = head;
ListNode p1 = newHead, p2 = p1;
while(p2.next!=null){
p2 = p2.next;
if(p2.next==null) break;
p2 = p2.next;
// switch
ListNode temp = p1.next;
p1.next = p2;
temp.next = p2.next;
p2.next = temp;
p1 = temp;
p2 = temp;
}
return newHead.next;
}
}
No comments:
Post a Comment