説明

リンクされたリストを指定して、隣接する 2 つのノードごとに交換し、その先頭を返します.

例 1:

Input: head = [1,2,3,4]
Output: [2,1,4,3]

例 2:

Input: head = []
Output: []

例 3:

Input: head = [1]
Output: [1]

制約:

リスト内のノード数は [0, 100] の範囲内です.

0 <= Node.val <= 100

解题

方法一

思路

非递归

代码

public ListNode swapPairs(ListNode head) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode current = dummy;
    while (current.next != null && current.next.next != null) {
        ListNode first = current.next;
        ListNode second = current.next.next;
        first.next = second.next;
        current.next = second;
        current.next.next = first;
        current = current.next.next;
    }
    return dummy.next;
}

复杂度分析

時間复杂度: O(n)

空間复杂度: O(1)

方法二

思路

グラフを描く

ダミー = 新しいノード

通貨 = ヘッド

前の = ダミー

prev.next = curr

prev.next = curr.next

curr.next = curr.next.next

prev.next.next = curr

前 = 前.次.次

curr = curr.next

実装

以下のようなグラフを描く必要があります

日 -> 1 -> 2 -> 3

d->2

1->3

2->1

d -> 2 -> 1 -> 3

代码

import java.util.*;

/**
 * class LLNode {
 *   int val;
 *   LLNode next;
 * }
 */
class Solution {
    public LLNode solve(LLNode node) {
        LLNode dummy = new LLNode();
        LLNode prev = dummy, curr = node;
        dummy.next = curr;
        // d -> 1 -> 2 -> 3 (prev=d,curr=1)
        while (curr != null && curr.next != null) {
            // d -> 2
            prev.next = curr.next;
            // 1 -> 3
            curr.next = curr.next.next;
            // 2 -> 1
            prev.next.next = curr;
            // prev = 1 (d -> 2 -> 1 -> 3)
            prev = prev.next.next;
            // curr = 3 (d -> 2 -> 1 -> 3)
            curr = curr.next;
        }
        return dummy.next;
    }
}

复杂度分析

時間复杂度: O(n)

空間复杂度: O(1)