24 swap node in pairs 链表 递归.md

---

---

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

You may not modify the values in the list’s nodes, only nodes itself
may be changed.

题目

初始解法（纯链表操作）

记录当前pair的first和second 记录下一个pair的first 把first.next连到下一个的second即可

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
if not head:
return None
if not head.next:
return head
    first <span class="token operator">=</span> head
    second <span class="token operator">=</span> first<span class="token punctuation">.</span><span class="token builtin">next</span>
    head <span class="token operator">=</span> head<span class="token punctuation">.</span><span class="token builtin">next</span><span class="token comment">#从第一个pair的second开始</span>
    
    <span class="token keyword">while</span> first <span class="token operator">and</span> first<span class="token punctuation">.</span><span class="token builtin">next</span><span class="token punctuation">:</span>
        next_first <span class="token operator">=</span> second<span class="token punctuation">.</span><span class="token builtin">next</span><span class="token comment">#下一个first节点</span>
        
        second<span class="token punctuation">.</span><span class="token builtin">next</span> <span class="token operator">=</span> first<span class="token comment">#倒叙连接</span>
        
        <span class="token keyword">if</span> <span class="token operator">not</span> next_first<span class="token punctuation">:</span><span class="token comment">#说明没有下一个pair</span>
            first<span class="token punctuation">.</span><span class="token builtin">next</span> <span class="token operator">=</span> <span class="token boolean">None</span>
            <span class="token keyword">break</span>
            
        <span class="token keyword">if</span> <span class="token operator">not</span> next_first<span class="token punctuation">.</span><span class="token builtin">next</span><span class="token punctuation">:</span><span class="token comment">#说明下一个pair只有一个节点</span>
            first<span class="token punctuation">.</span><span class="token builtin">next</span> <span class="token operator">=</span> next_first
            <span class="token keyword">break</span>
            
        first<span class="token punctuation">.</span><span class="token builtin">next</span> <span class="token operator">=</span> next_first<span class="token punctuation">.</span><span class="token builtin">next</span><span class="token comment">#first是当前pair的结束 连接到下一个pair的second节点 也就是下一个pair的开始</span>
        <span class="token comment">#更新first和second节点到下一个pair</span>
        first <span class="token operator">=</span> next_first
        second <span class="token operator">=</span> first<span class="token punctuation">.</span><span class="token builtin">next</span>
        
    <span class="token keyword">return</span> head

也可以使用一个哑节点来避免对特殊情况的判断

递归

递归终止条件：当前pair没有节点或者只有一个节点
递归的工作：

1. 颠倒当前pair的链接顺序
2. 给当前pair的first节点连接下一个pair
3. 返回second节点供上一个pair连接

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
if not head or not head.next:
return head
    second <span class="token operator">=</span> head<span class="token punctuation">.</span><span class="token builtin">next</span>
    head<span class="token punctuation">.</span><span class="token builtin">next</span> <span class="token operator">=</span> self<span class="token punctuation">.</span>swapPairs<span class="token punctuation">(</span>second<span class="token punctuation">.</span><span class="token builtin">next</span><span class="token punctuation">)</span>
    second<span class="token punctuation">.</span><span class="token builtin">next</span> <span class="token operator">=</span> head
    <span class="token keyword">return</span> second