24. 两两交换链表中的节点

递归

/**
 * 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 next = head.next;
        // 递归交换两个节点
        head.next = swapPairs(next.next);
        next.next = head;
        return next;
    }
}

• 时间复杂度 O(n)
• 空间复杂度 O(n)

迭代

/**
 * 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 dummy = new ListNode(0);
        dummy.next = head;
        ListNode p = dummy;
        // 迭代交换两个节点
        while (p.next != null && p.next.next != null) {
            ListNode node1 = p.next;
            ListNode node2 = p.next.next;
            p.next = node2;
            node1.next = node2.next;
            node2.next = node1;
            p = node1;
        }
        return dummy.next;
    }
}

• 时间复杂度 O(n)
• 空间复杂度 O(1)