Leetcode 24. Swap Nodes in Pairs

給定一個鍊錶，將每兩個相鄰的節點進行交換，並返回交換後的鍊錶。不能只是單純的改變節點內部的值，而是需要實際的進行節點交換。

Python

方法一 : 遞迴

算法流程：

如果鍊錶為空或者只有一個節點，則無需交換。
交換前兩個節點。
遞歸地對剩餘的節點進行交換。
遞歸地對剩餘的節點進行交換。

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        # 如果鍊錶為空或者只有一個節點，則無需交換
        if not head or not head.next:
            return head

        # 交換前兩個節點
        first_node = head
        second_node = head.next
        first_node.next = self.swapPairs(second_node.next)
        second_node.next = first_node

        # 返回交換後的鍊錶
        return second_node

方法二：迭代兩兩交換

如果只有一個節點或者沒有節點，直接返回head。while 循環判斷當head 和head.next 都不為空的情況下

（1）tail 保存第三個及之後的鍊錶

（2）使用tmp 臨時保存head.val

（3）將head.next.val 賦予head.val 表示將後一個節點的值賦給前一個節點

（4）將tmp 賦予head.next.val 表示將前一個節點的值賦予後一個節點

這樣兩個節點的值就完成了互換判斷第三個和第四個節點是否都存在，如果是，則將tail 賦予head ，表示下一次循環交換第三個和第四個節點的值，否則直接返回result

class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution(object):
    def swapPairs(self, head):
        
        if not head or not head.next: return head
        result = head
        while head and head.next:
            tail = head.next.next      #tail 保存第三個及之後的鍊錶
            tmp = head.val             #使用tmp 臨時保存head.val
            head.val = head.next.val   #將head.next.val 賦予head.val 表示將後一個節點的值賦給前一個節點
            head.next.val = tmp        #將tmp 賦予head.next.val 表示將前一個節點的值賦予後一個節點
            if tail and tail.next:
                head = tail
            else:
                break
        return result

每次記錄兩個節點數值交換，之後再將兩個節點指標往後移動

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next: return head
        prev = head
        cur  = head.next

        while prev and cur:
            # 「兩兩節點的數值交換」
            temp = prev.val;
            prev.val = cur.val;
            cur.val = temp;

            if not cur.next or not cur.next.next:
                break

            # 「兩兩節點的鏈結」
            prev = cur.next;
            cur  = cur.next.next;     
        
        return head

C++

遞歸:

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }
        ListNode *res = head->next; //res指向head->next
        head->next = swapPairs(head->next->next); //head.next指向遞歸
        res->next = head; //res.next指向head
        return res;
    }
};

Python

C++

相關