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.
/**
* 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) {
// Start typing your Java solution below
// DO NOT write main() function
ListNode helper = new ListNode(0);
helper.next = head;
ListNode n1 = helper, n2=head;
while(n2!=null && n2.next!=null){
ListNode temp = n2.next.next;
n2.next.next=n1.next;
n1.next=n2.next;
n2.next=temp;
n1=n2;
n2=n1.next;
}
return helper.next;
}
}
5 comments:
This is the best solution I have seen so far, thank for sharing.
Glad to hear!
some one do it iteratively.
https://github.com/mengli/leetcode/blob/master/Swap%20Nodes%20in%20Pairs.java
class Solution {
public:
/** 2/4/2014 */
ListNode *swapPairs(ListNode *head) {
if (!head || !head->next) return head;
ListNode *newHead = head->next;
head->next = head->next->next;
newHead->next = head;
ListNode *curr = newHead->next, *n1, *n2;
while (curr->next && curr->next->next) {
n1 = curr->next;
n2 = n1->next;
curr->next = n2;
n1->next = n2->next;
n2->next = n1;
curr = n1;
}
return newHead;
}
};
Here's my code. No additional node needed. Just take care of first two nodes at first and do the normal loop from the third one to the last one. The advantage of this is to avoid memory dealloc in c/c++, which causes memory leak.
Genius!
Post a Comment