題目24. 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.
1,遞歸
public class Solution {
public ListNode swapPairs(ListNode head) {
ListNode tempHead = new ListNode(1);
ListNode tail = tempHead;
reverse(head,tail);
return tempHead.next;
}
private void reverse(ListNode head, ListNode tail){
if(head == null || head.next == null){
tail.next = head;
return;
}
ListNode preNode = head;
ListNode nextNode = head.next;
ListNode temp = nextNode.next;
tail.next = nextNode;
tail = tail.next;
tail.next = preNode;
tail = tail.next;
reverse(temp,tail);
}
2,非遞歸
public ListNode swapPairs(ListNode head) {
if(head == null || head.next == null){
return head;
}
ListNode tempHead = new ListNode(1);
ListNode tail = tempHead;
ListNode preNode = head;
ListNode nextNode = preNode.next;
while(preNode != null && nextNode != null){
ListNode temp = nextNode.next;
tail.next = nextNode;
tail = tail.next;
tail.next = preNode;
tail = tail.next;
preNode = temp;
if(preNode == null){
break;
}
nextNode = preNode.next;
}
tail.next = preNode;
return tempHead.next;
}
