P210 两两交换链表中的节点

描述#

这个题目说的是，给你一个单链表，你要以每两个相邻的节点为一组，交换两个节点的位置，然后返回处理后的链表。

注意，不允许修改节点中的数值，只能通过修改节点的 next 指针来改变链表结构。

比如说，给你的链表是：
1 -> 2 -> 3 -> 4
两两交换相邻的节点后，得到：
2 -> 1 -> 4 -> 3
再比如说，给你的链表是：
1 -> 2 -> 3 -> 4 -> 5
两两交换相邻的节点后，得到：
2 -> 1 -> 4 -> 3 -> 5

代码#

public class AlgoCasts {

  public class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
      val = x;
    }
  }

  // Time: O(n), Space: O(n)
  public ListNode swapPairsRecursive(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode next = head.next;
    head.next = swapPairsRecursive(next.next);
    next.next = head;
    return next;
  }

  // Time: O(n), Space: O(1)
  public ListNode swapPairsIterative(ListNode head) {
    ListNode dummy = new ListNode(0), pre = dummy;
    dummy.next = head;
    while (pre.next != null && pre.next.next != null) {
      ListNode first = pre.next, second = pre.next.next;
      pre.next = second;
      first.next = second.next;
      second.next = first;
      pre = first;
    }
    return dummy.next;
  }

}