12.2 链表的基本操作

# 12.2 链表的基本操作

## [206. Reverse Linked List](https://leetcode.com/problems/reverse-linked-list/)

### 题目描述

翻转一个链表。

### 输入输出样例

输入一个链表，输出该链表翻转后的结果。

```
Input: 1->2->3->4->5->nullptr
Output: 5->4->3->2->1->nullptr
```

### 题解

链表翻转是非常基础也一定要掌握的技能。我们提供了两种写法——递归和非递归。建议你同时掌握这两种写法。

递归的写法为：

```py
def reverseList(
    head: Optional[ListNode], pre: Optional[ListNode] = None
) -> Optional[ListNode]:
    if head is None:
        return pre
    nxt = head.next
    head.next = pre
    return reverseList(nxt, head)
```

非递归的写法为：

```py
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        pre = None
        cur = head
        while cur:
            nxt = cur.next
            cur.next = pre
            pre = cur
            cur = nxt
        return pre
```

## 21. 合并两个有序链表
[21. Merge Two Sorted Lists](https://leetcode.cn/problems/merge-two-sorted-lists)

### 题目描述

给定两个增序的链表，试将其合并成一个增序的链表。

### 输入输出样例

输入两个链表，输出一个链表，表示两个链表合并的结果。

```
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4
```

### 题解

我们提供了递归和非递归，共两种写法。递归的写法为：

```py
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if not list1 or not list2:
            return list1 or list2
        if list1.val < list2.val:
            list1.next = self.mergeTwoLists(list1.next, list2)
            return list1
        else:
            list2.next = self.mergeTwoLists(list1, list2.next)
            return list2
```

```py
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode()
        head = dummy
        while list1 and list2:
            if list1.val < list2.val:
                head.next = list1
                list1 = list1.next
            else:
                head.next = list2
                list2 = list2.next
            head = head.next
        head.next = list1 or list2
        return dummy.next

```

## 24. 两两交换链表中的节点
[24. Swap Nodes in Pairs](https://leetcode.cn/problems/swap-nodes-in-pairs/)

### 题目描述

给定一个矩阵，交换每个相邻的一对节点。

### 输入输出样例

输入一个链表，输出该链表交换后的结果。

```
Input: 1->2->3->4
Output: 2->1->4->3
```

### 题解

利用指针进行交换操作，没有太大难度，但一定要细心。

直接交换
```py
class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        node0 = dummy = ListNode(next = head)
        node1 = head
        while node1 and node1.next:
            node2 = node1.next
            node3 = node2.next

node0.next = node2
            node2.next = node1
            node1.next = node3

node0 = node1
            node1 = node3
        return dummy.next
```
递归
```py
class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:return head
        
        node1 = head
        node2 = head.next
        node3 = node2.next

node1.next = self.swapPairs(node3)
        node2.next = node1

return node2
```