---
title: 【LeetCode】0024. Swap Nodes in Pairs
date: 2019-06-17
is_modified: false
disqus: cynthiahackmd
categories:
- "面試刷題"
tags:
- "LeetCode"
---

{%hackmd @CynthiaChuang/Github-Page-Theme %}

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

<!--more-->
<br>

**Example:**

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

<br>

> **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.
>

<br>

**Related Topics:** `Linked List`

## 解題邏輯與實作
這題是要以兩個節點為一組翻轉鏈結陣列，難度不高，但很容易把自己搞暈頭轉向，建議先畫圖輔助會比較清楚。

## 迭代
這個的想法比較簡單，就是兩兩指標交換，不過在交換時需要注意下交換的順序，不然很容易把指標搞丟了。

class Solution:
   def swapPairs(self, head):
      dummy_head = ListNode(-1)
      dummy_head.next = head
      iteration = dummy_head

      while iteration.next and iteration.next.next :
         node1 = iteration.next
         node2 = iteration.next.next

         iteration.next = node2
         node1.next = node2.next
         node2.next = node1

         iteration = iteration.next.next

      return dummy_head.next        

## 遞迴
想說迭代做的到的，應該也可以用遞迴來實做。實做時，先交換最後兩個，再依序向前交換。

class Solution:
   def swapPairs(self, head):
      if not head or not head.next:
            return head

      node = head.next
      head.next = self.swapPairs(head.next.next)
      node.next = head

      return node          

## 其他連結
1. [【LeetCode】0000. 解題目錄](/x62skqpKStKMxRepJ6iqQQ)

<br><br>

> **本文作者**： 辛西亞．Cynthia
> **本文連結**： [辛西亞的技能樹](https://cynthiachuang.github.io/LeetCode-0024-Swap-Nodes-in-Pairs) / [hackmd 版本](https://hackmd.io/@CynthiaChuang/LeetCode-0024-Swap-Nodes-in-Pairs)
> **版權聲明**： 部落格中所有文章，均採用 [姓名標示-非商業性-相同方式分享 4.0 國際](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.en) (CC BY-NC-SA 4.0) 許可協議。轉載請標明作者、連結與出處！