Tuesday, January 6, 2015

Swap Nodes in Pairs (LeetCode Linked List)

Question: 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.

Idea: I used recursion. First recursively swap the sub-list starting from head.next.next. Then swap head.next and head.

Time: O(n) Space: O(1)

Code: 
 public class Solution {  
   public ListNode swapPairs(ListNode head) {  
     if(head==null||head.next==null)  
       return head;  
     head.next.next=swapPairs(head.next.next);  
     ListNode newHead=head.next;  
     head.next=head.next.next;  
     newHead.next=head;  
     return newHead;  
   }  
 }  

No comments:

Post a Comment