leetcode-24-swap-nodes-in-pairs

Description

Given a linked list, swap every two adjacent nodes and return its head.

Example:

1	Given 1->2->3->4, you should return the list as 2->1->4->3.

Note:

Your algorithm should use only constant extra space.
You may not modify the values in the list’s nodes, only nodes itself may be changed.

####思路0

題意是讓妳交換鏈表中相鄰的兩個節點，最終返回交換後鏈表的頭，限定妳空間復雜度為$ O(1)$。我們可以用遞歸來算出子集合的結果，遞歸的終點就是指針指到鏈表末少於兩個元素時，如果不是終點，那麽我們就對其兩節點進行交換，這裏我們需要一個臨時節點來作為交換橋梁，就不多說了。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode node = head.next;
        head.next = swapPairs(node.next);
        node.next = head;
        return node;
    }
}

思路1

另一種實現方式就是用循環來實現了，兩兩交換節點，也需要一個臨時節點來作為交換橋梁，直到當前指針指到鏈表末少於兩個元素時停止

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode prev = new ListNode(0), curr = prev;
        prev.next = head;
        while (curr.next != null && curr.next.next != null) {
            ListNode nextTemp = curr.next.next;
            cur.next.next = nextTemp.next;
            nextTemp.next = curr.next;
            curr.next = temp;
            cur = curr.next.next;
        }
        return prev.next;
    }
}