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.
Solution
这题的核心在于dummy node和list操作。
dummy -> 1 -> 2 -> 3 -> 4
prev cur next tmp
我们用四个指针来完成操作。
1. 预存tmp: tmp = next.next
2. 更改next: next.next = cur
3. 更改cur: cur.next = tmp
4. 更改prev: prev.next = next
5. 更新prev, cur, next:
cur = tmp
if (cur != null): next = cur.next
prev = prev.next.next
最后返回dummy.next
我们看到循环结束的条件应该是tmp为null或者tmp.next为null.
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode swapPairs(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode prev = dummy, current = head, next = head.next, tmp;
while (next != null) {
tmp = next.next;
next.next = current;
current.next = tmp;
prev.next = next;
current = tmp;
prev = prev.next.next;
if (current == null) {
break;
} else {
next = current.next;
}
}
return dummy.next;
}
}