算法训练之 -- 反转链表

反转链表

1. 思路

  给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。206. 反转链表 - 力扣（LeetCode）

思路：反转链表可以使用 迭代 和 递归 的方法实现。

  1. 迭代：假设链表为 1→2→3→∅1，想要把它改成 ∅←1←2←3。在遍历链表时，将当前节点的 next 指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用。

  2. 使用递归法遍历链表，当越过尾节点后终止递归，在回溯时修改各节点的 next 引用指向。

    • recur(cur, pre) 递归函数： 终止条件：当 cur 为空，则返回尾节点 pre （即反转链表的头节点）； 递归后继节点，记录返回值（即反转链表的头节点）为 res ； 修改当前节点 cur 引用指向前驱节点 pre ； 返回反转链表的头节点 res 。
    • reverseList(head) 函数： 调用并返回 recur(head, null) 。传入 null 是因为反转链表后， head 节点指向 null 。

2. 解法一

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        cur, pre = head, None
        while cur:
            tmp = cur.next # 暂存后继结点
            cur.next = pre  # 修改 cur 后继结点的指向
            pre = cur   # pre 暂存 cur
            cur = tmp   # cur 访问下一个节点
        
        return pre

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * 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* reverseList(ListNode* head) {
        ListNode* cur = head;
        ListNode* pre = NULL;
        ListNode* tmp;
        while(cur != NULL){
            tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
};

2. 解法二

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        def recur(cur, pre):
            if not cur:
                return pre               # 终止条件
            res = recur(cur.next, cur)   # 递归后继节点
            cur.next = pre               # 修改节点引用指向
            return res                   # 返回反转链表的头节点

        return recur(head, None)         # 调用递归并返回

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        return  recur(head, nullptr);   // 调用递归并返回
    }
private:
    ListNode* recur(ListNode* cur, ListNode* pre){
        if(cur == nullptr)
            return pre; // 终止条件
        ListNode* res = recur(cur->next, cur);  // 递归后继节点
        cur->next = pre; // 修改节点引用指向
        return res;     // 返回反转链表的头节点
    }    
};

3. 变种

(1) 题目：给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。92. 反转链表 II - 力扣（LeetCode）

思路：

  1. 记录需要反转部分位置的前一个节点和后一个节点， pre 和 curr，然后通过遍历找到 反转部分的 left 和 right 节点，将这部分截断之后，调用反转链表函数，可以使用迭代或者递归，最后将 pre 的下一个节点指向 right ，left 的下一个节点指向 curr 。

  2. 在需要反转的区间里，每遍历到一个节点，让这个新节点来到反转部分的起始位置。

    使用三个指针变量 pre、curr、next 来记录反转的过程中需要的变量，它们的意义如下：

    • curr：指向待反转区域的第一个节点 left；
    • next：永远指向 curr 的下一个节点，循环过程中，curr 变化以后 next 会变化；
    • pre：永远指向待反转区域的第一个节点 left 的前一个节点，在循环过程中不变。

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        # 反转链表函数
        def reverse_linked_list(head: ListNode):
            pre = None
            cur = head
            while cur:
                next = cur.next
                cur.next = pre
                pre = cur
                cur = next
        # 使用虚拟头结点， 防止头结点发生变化，同时在遍历时更加方便
        dummy_node = ListNode(-1)
        dummy_node.next = head
        pre = dummy_node
        # 第 1 步：从虚拟头节点走 left - 1 步，定位到 left 节点的前一个节点
        for _ in range(left-1):
            pre = pre.next
        # 第 2 步：从 pre 再走 right - left + 1 步，定位到 right 节点
        right_node = pre
        for _ in range(right - left + 1):
            right_node = right_node.next
        # 第 3 步：切断出一个子链表（截取链表）
        left_node = pre.next    # 需要反转的链表的第一个节点
        curr = right_node.next  # 记录反转链表最后节点的后一个节点，用于反转后拼接
        # 切断链表
        pre.next = None # 反转链表的前一个节点
        right_node.next = None  # 反转链表的最后一个节点

        reverse_linked_list(left_node)  # 反转链表

        pre.next = right_node   # 拼接反转后的节点
        left_node.next = curr

        return dummy_node.next
    
# 一次遍历
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        dummy_node = ListNode(-1)
        dummy_node.next = head
        pre = dummy_node
        for _ in range(left-1):	# 定位到反转部分的前一个节点
            pre = pre.next

        cur = pre.next	# 指向反转部分的第一个节点
        # 每次将反转链表的下一个节点放置第一个节点前
        for _ in range(right-left):
            next = cur.next			
            cur.next = next.next
            next.next = pre.next
            pre.next = next
        
        return dummy_node.next

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/**
 * 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 {
private:
    void reverseLinkedList(ListNode *head){

        ListNode *pre = nullptr;
        ListNode *cur = head;
        ListNode *tmp;
        while(cur != nullptr){
            tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }
    }
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        ListNode *dummy_node = new ListNode(-1);
        dummy_node->next = head;

        ListNode *pre = dummy_node;

        for(int i=0; i<left-1; i++)
            pre = pre->next;

        ListNode *right_node = pre;
        for(int i=0; i<right-left+1; i++)
            right_node = right_node->next;

        ListNode *left_node = pre->next;
        ListNode *curr = right_node->next;

        pre->next = nullptr;
        right_node->next = nullptr;

        reverseLinkedList(left_node);

        pre->next = right_node;
        left_node->next = curr;
        return dummy_node->next;
    }
};

(2) 题目：编写一个函数，检查输入的链表是否是回文的。

思路：

  1. 将值复制到数组中后用双指针法

    （1）复制链表值到数组列表中。（2）使用双指针法判断是否为回文。

  2. 递归

    不想看递归。。。

  3. 快慢指针

    （1）找到前半部分链表的尾节点。（2）反转后半部分链表。（3）判断是否回文。（4）恢复链表。（5）返回结果。

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
# 复制链表的值，然后使用双指针

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        vals = []
        cur = head
        while cur:
            vals.append(cur.val)
            cur = cur.next
        return vals == vals[::-1]
    
# 快慢指针

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        
        if head is None:
            return True

        first_half_end = self.end_of_first_half(head)
        second_half_start = self.reverse_list(first_half_end.next)
		
        # 用前半部分 和 反转之后的后半部分进行比较判断
        ans = True
        first_index = head
        second_index = second_half_start
        while ans and second_index is not None:
            if first_index.val != second_index.val:
                ans = False
            first_index = first_index.next
            second_index = second_index.next
        
        first_half_end.next = self.reverse_list(second_half_start)
        return ans
    
    '''
    慢指针一次走一步，快指针一次走两步，快慢指针同时出发。
    当快指针移动到链表的末尾时，慢指针恰好到链表的中间。通过慢指针将链表分为两部分。
    '''
    def end_of_first_half(self, head):	
        fast = head
        slow = head
        while fast.next is not None and fast.next.next is not None:
            fast = fast.next.next
            slow = slow.next
        return slow 
    
    # 反转链表
    def reverse_list(self, head):
        pre = None
        cur = head
        while cur:
            tmp = cur.next
            cur.next = pre
            pre = cur
            cur = tmp
        
        return pre

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
/**
 * 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:
    bool isPalindrome(ListNode* head) {

        if(head == nullptr){
            return true;
        }

        ListNode* firstHalfEnd = endOfFirstHalf(head);
        ListNode* secondHalfStart = reverseList(firstHalfEnd->next);

        ListNode* first = head;
        ListNode* second = secondHalfStart;
        bool ans = true;
        while(ans && second != nullptr){
            if(first->val != second->val){
                ans = false;
            }
            first = first->next;
            second = second->next;
        }
        firstHalfEnd->next = reverseList(secondHalfStart);
        return ans;
    }

    ListNode* reverseList(ListNode* head){
        ListNode* prev = nullptr;
        ListNode* curr = head;
        ListNode* tmp = nullptr;
        while(curr != nullptr){
            tmp = curr->next;
            curr->next = prev;
            prev = curr;
            curr = tmp;
        }
        return prev;
    }

    ListNode* endOfFirstHalf(ListNode* head){
        ListNode* slow = head;
        ListNode* fast = head;
        while(fast->next != nullptr && fast->next->next != nullptr){
            fast = fast->next->next;
            slow = slow->next;
        }
        return slow;
    }
};
算法
#刷题
算法训练之 -- 反转链表
http://seulqxq.top/posts/37946/
作者
SeulQxQ
发布于
2024年2月5日
许可协议