LeetCode 解題練習：Swap Nodes in Pairs

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

If you like this post, please click the ads on the blog or buy me a coffee. Thank you very much.

題目原文描述 https://leetcode.com/problems/swap-nodes-in-pairs/

中文描述

給定一個鏈結串列(linked list)，將兩個相鄰節點交換後回傳開頭的節點。注意不得修改節點內的值。

範例一：

輸入 head = [1, 3, 5, 7]

輸出 [3, 1, 7, 5]

解法：

用一個變數 t 作為交換相鄰兩個節點的暫時替代空間，用來交換第一個節點 head 與 第二個節點head.next 。依照下列步驟來交換相鄰的兩個節點：

1. t 先設定為 head.next。 
2. head.next 設定為 swap(t.next)。
3. t.next 設定為 head。

Python Code

# Definition for singly-linked list.

# class ListNode:

#     def __init__(self, val=0, next=None):

#         self.val = val

#         self.next = next

class Solution:

    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:

        if head == None or head.next == None: # 目前節點或下一個節點為 None

            return head # 傳回 head

        t = head.next # 節點 t 指向目前的相鄰的第二個節點

        head.next = self.swapPairs(t.next) # 目前節點指向下一組交換完的第一個節點

        t.next = head # 節點 t 指向目前的相鄰的第一個節點

        return t # 傳回相鄰的第一個節點

C++ Code

/**

 * Definition for singly-linked list.

 * struct ListNode {

 *     int val;

 *     ListNode *next;

 *     ListNode() : val(0), next(nullptr) {}

 *     ListNode(int x) : val(x), next(nullptr) {}

 *     ListNode(int x, ListNode *next) : val(x), next(next) {}

 * };

 */

class Solution {

public:

    ListNode* swapPairs(ListNode* head) {

        if( head == nullptr || head->next == nullptr) // 目前節點或下一個節點為 null

            return head; // 回傳 head

       

        ListNode *t = head->next; // 節點 t 指向目前的相鄰的第二個節點

        head->next = swapPairs(t->next); // 目前節點指向下一組交換完的第一個節點

        t->next = head; // 節點 t 指向目前的相鄰的第一個節點

        return t; // 傳回相鄰的第一個節點

    }

};