关于链表类型题目的总结

Python3 单向链表基础代码

声明链表节点

四行代码声明链表节点 written by hand require

class ListNode():             # 1
    def __init__(self, val):  # 2
        self.val = val        # 3
        self.next = None      # 4

    def __str__(self):
        return str(self.val)

创建链表

10行代码创建链表 written by hand require

def createList(nums: list) -> ListNode: # 10
    """Create Linked List
    :type nums: Python List
    :rtype: ListNode
    """
    if len(nums):                       # 1
        root = ListNode(nums[0])        # 2
    else:                               # 3
        return None                     # 4
    tmp = root                          # 5
    for i in range(1, len(nums)):       # 6
        tmp.next = NodeList(nums[i])    # 7
        tmp = tmp.next                  # 8
    return root                         # 9

加上了特判的版本

def createList(value_list: list) -> ListNode:
    """Create Linked List based on list
    :param value_list: list
    :return: NodeList
    """
    _len = len(value_list)
    if _len == 0:
        return None
    if _len == 1:
        return ListNode(value_list[0])
    else:
        root = ListNode(value_list[0])
        tmp = root
        for i in range(1, _len):
            # 声明当前节点，再把当前节点与前面节点联系在一起。
            tmp.next = ListNode(value_list[i])
            tmp = tmp.next  # 更新tmp
    return root # 返回根节点

逐个输出链表节点

def printList(head: ListNode):
    """Print single node one by one in linked list
    :param head: ListNode
    :return: None
    """
    p = head
    while p != None:
        # print()
        print(p)  # 由于有ListNode实现了__str__函数 就不用调用p.val来获取节点值了
        p = p.next

获取链表长度

7行代码获取链表长度 written by hand require

def listLength(head: ListNode) -> int: # 7
    """Get the length of linked list
    :param head: ListNode
    :return: int
    """
    count = 0        # 1
    p = head         # 2
    while p != None: # 3
        count += 1   # 4
        p = p.next   # 5
    return count     # 6

插入ListNode

12行代码实现链表节点插入（注意 while local != 1: 的条件） written by hand require

def insertList_V1(head: ListNode, local: int, val: int) -> ListNode:  # 1
    """Insert ListNode
    :param head: ListNode
    :param local: int
    :param val: int
    :return: ListNode
    """ 
    if local < 0 or local > listLength(head):  return  # 2
    dummy = ListNode(None)                             # 3
    dummy.next = head                                  # 4
    p = dummy                                          # 5
    while local != 1:                                  # 6
        p = p.next                                     # 7
        local -= 1                                     # 8
    tmp_node = ListNode(val)                           # 9
    tmp_node.next = p.next                             # 10
    p.next = tmp_node                                  # 11

    return dummy.next                                  # 12

一个不使用哑节点的方法

def insertList(head: ListNode, local: int) -> ListNode:
    """Instert ListNode into certain current linked list
    :param head: ListNode
    :param local: int (index start from 1)
    :return: ListNode
    """
    if local < 0 or local > listLength(head):  return  head
    insert_value = input("Enter a val: ")              
    if local == 1:  # 插到第一个位置 其他节点自动后移
        tmp_Node = ListNode(insert_value)
        tmp_Node.next = head
        return tmp_Node
    # 否则插入位置大于1
    p = head
    # 循环n次达到n+1 所以这里是local != 2 而不是local != 1 插入的位置，实际上是要找到插入位置的前序位置。
    while local != 2:
        p = p.next
        local -= 1
    tmp_Node = ListNode(insert_value)
    tmp_Node.next = p.next
    p.next = tmp_Node

    return head

删除ListNode

10行代码实现删除链表节点（注意这个删除操作的写法 p.next = p.next.next） written by hand require

def deleteListNode(head: ListNode, local: int) -> ListNode:  # 1
    """Remove the certain ListNode in the linked list
    :param head: ListNode
    :param local: int
    :return ListNode:
    """
    if local < 0 or local > listLength(head):  return head  # 2
    dummy = ListNode(None)                                  # 3
    dummy.next = head                                       # 4
    p = dummy                                               # 5
    while local != 1:                                       # 6
        p = p.next                                          # 7
        local -= 1                                          # 8
    p.next = p.next.next                                    # 9

    return dummy.next                                       # 10

一个不使用哑节点的版本

def deleteList(head: ListNode, local: int) -> ListNode:
    """Remove the certain ListNode in the linked list
    :param head: ListNode
    :param local: int
    :return ListNode:
    """
    if local < 1 or local > listLength(head):  # 待删除节点不在链表中 直接返回
        return head
    elif local == 1:
        head = head.next
    else:
        p = head
        while local != 2:
            p = p.next
            local -= 1
        tmp_p = p.next
        p.next = tmp_p.next
    return head

链表反转

递归 6行代码

def reverseList(head: ListNode) -> ListNode:            # 1
    """reverse Linked List
    :param head: ListNonde
    :return: ListNonde
    """
    if head == None or head.next == None:  return head  # 2
    p = reverseList(head.next)                          # 3
    head.next.next = head                               # 4
    head.next = None                                    # 5
    return p                                            # 6

循环 13行 代码

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:       # 1
        """reverse Linked List
        :param head: ListNonde
        :return: ListNonde
        """
        if head == None or head.next == None:  return head   # 2
        dummy = ListNode(None)                               # 3
        dummy.next = head                                    # 4
        pre_p = dummy                                        # 5
        p = head                                             # 6
        while p:                                             # 7
            next_p = p.next                                  # 8
            p.next = pre_p                                   # 9
            pre_p = p                                        # 10
            p = next_p                                       # 11
        # 完成反转之后要把head.next设置为None。防止循环链表出现。
        head.next = None                                     # 12
        return pre_p                                         # 13

LinkedList 转Python List

def convert2list(head: ListNode) -> list:
    """Convert linked list to normal list
    :param head: ListNonde
    :return: list
    """
    res = []
    p = head
    while p != None:
        res.append(p.val)  # 由于有ListNode实现了__str__函数 就不用调用p.val来获取节点值了
        p = p.next
    return res

主函数

def main():
    value_list = [1, 2, 3, 4, 5]
    print("Create a Linklist: ")
    head = createList(value_list)
    print("Length of LinkedListed: {}".format(listLength(head)))
    printList(head)
    print("-"*50)
  
    n1 = input("Enter the index to insert(start form 1): ")
    n1 = int(n1)
    insert_val = input("Enter a val: ") 
    head = insertList_V1(head, n1, insert_val)
    print("Length of LinkedList: {}".format(listLength(head)))
    printList(head)
    print("-"*50)
  
    n2 = input("Enter the index to delete(start form 1): ")
    n2 = int(n2)
    head = deleteList(head, n2)
    print("Length of LinkedList: {}".format(listLength(head)))
    printList(head)


if __name__=='__main__':
	main()   # 主函数调用

C++ 单向链表基础代码

先声明引用和命名空间

#include <vector>
#include <iostream>

using namespace std;

声明链表节点

// 基于类对ListNode进行声明 面向对象编程思想
class ListNode {
    public:
        int val;
        ListNode *next;

         // 第二个参数默认值为NULL，如果创建新节点时只指定第一个参数，而不写第二个参数，默认的就是NULL。
        ListNode(int val = 0, ListNode *p = NULL) {
            this->val = val;
            this->next = p;
        }
};

// 以下是LeetCode的定义的Node节点 基于C++结构体的形式 函数编程思想
// 第一种形式
// Definition for singly-linked list.
// struct ListNode {
//     int val;
//     ListNode *next;
//     ListNode(int x) : val(x), next(NULL) {}
// };
// 第二种形式
// typedef struct ListNode{
//     int val;
//     struct ListNode* next;
//     ListNode(int x) :
//         val(x), next(NULL){
//     }
// };

声明LinkedList结构

class LinkedList{
    private:
        ListNode *head, *tail;
    
    public:
        LinkedList(){head=tail=NULL;};             // 构造函数
        ~LinkedList(){delete head; delete tail;};  // 析构函数
        void print();                              // 输出链表结果
        void Insert(int val=0);                    // 尾插法插入单个节点
        void Delete(int val=0);                    // 删除单个节点
        void Search(int val=0);                    // 在链表上搜索某个值是否存在
        int getValueAt(int position);              // 获得链表上某个位置的值
        void setValueAt(int postion, int val);     // 设置链表上某个位置的值
        void Create(vector<int> nums);             // 输入vector<int>创建链表
        void Reverse();                            // 将链表翻转
        int getLength();                           // 获取链表长度
};

创建链表

void LinkedList::Create(vector<int> nums){
    int n = nums.size();
    for(int i=0; i<n; i++){
        Insert(nums[i]);
    }
}

逐个输出链表节点

void LinkedList::print(){
    ListNode *p = head;
    while (p!=NULL){
        cout << p->val << " \a";
        p = p->next;
    }
    cout << endl;
}

获取链表长度

int LinkedList::getLength(){
    if(this->head==NULL)  return 0;
    int count = 0;
    ListNode *p = head;
    while(p!=NULL){
        count++;
        p = p->next;
    }
    return count;
}

插入ListNode

void LinkedList::Insert(int val){
    if(head==NULL){  // 空链表
        head = tail = new ListNode(val);  // 如果是第一次插入，要选择初始化。
        head->next = NULL;
        tail->next = NULL;
    }else{  // 有数值链表
        ListNode* p = new ListNode(val);
        tail->next = p;
        tail = p;
        tail->next = NULL;
    }
}

删除ListNode

void LinkedList::Delete(int val){
    ListNode *p = head, *q = head;
    if (p==NULL){
        cout << "Sorry, The List is Empty!" << endl;
        return;
    }
    while (p != NULL && p->val != val){
        q = p;
        p = p->next;
    }
    q->next = p->next;
    cout << "The Deletion Operation had been finished!" << endl;
}

链表反转

void LinkedList::Reverse(){
    if(this->head==NULL)  return;
    // 第一次扫描
    ListNode *dummy = new ListNode(0);
    dummy->next = this->head;
    ListNode *pre_p = dummy;
    ListNode *p = head;
    ListNode *next_p;
    while(p!=NULL){
        next_p = p->next;
        p->next = pre_p;
        pre_p = p;
        p = next_p;
    }
    this->head->next = NULL;
    this->head = pre_p;
}

搜索链表

void LinkedList::Search(int val){
    ListNode* p =  head;
    if(p==NULL){
        cout << "There is no postition in this List!" << endl;
        return;
    }
    int counter = 0;
    while(p != NULL && p->val != val){
        p = p->next;
        counter++;
    }
    cout << "the value you want to search is at position " << counter << endl;
}

获取特定节点上的值

int LinkedList::getValueAt(int position){
    ListNode* p = head;
    if(p == NULL){
        std::cout << "It is an empty Linked List!" << endl;
    }else{
        int posi = 0;
        while (p!= NULL && posi != position){
            posi++;
            p = p->next;
        }
        if (p == NULL){
            cout << "There is no value of this postition in this List!" << endl;
        }else{
            cout << "In this Position, the vuale is " << p->val << endl;
        }
    }
    return p->val;
}

设置特定节点上的值

void LinkedList::setValueAt(int position, int val){
    ListNode* p = head;
    if(p == NULL){
        cout << "It is an empty Linked List!" << endl;
    }else{
        int posi = 0;
        while (p!= NULL && posi != position){
            posi++;
            p = p->next;
        }
        if (p == NULL){
            cout << "There is no value of this postition in this List!" << endl;
        }else{
            p->val = val;
            cout << "The Value in this position has been Updated!" << endl;
        }
    }
}

主函数

int main(){
    cout << "***************************"  << endl;
    cout << "创建链表开始" << endl;
    LinkedList l1;
    vector<int> nums = {1, 2, 3, 4, 5, 6, 7, 8};
    l1.Create(nums);
    cout << "输出Linked List创建结果" << endl;
    l1.print();

    cout << "***************************"  << endl;
    cout << "获取链表长度为 " << l1.getLength() << endl;

    cout << "***************************"  << endl;
    int insert_element = 100;
    cout << "插入Linked List!" << insert_element << endl;
    l1.Insert(insert_element);
    cout << "输出Linked List插入结果" << endl;
    l1.print();

    cout << "***************************"  << endl;
    int delete_element = 7;
    cout << "删除Linked List " << delete_element << "!" << endl;
    l1.Delete(delete_element);
    cout << "输出Linked List删除结果" << endl;
    l1.print();

    cout << "***************************"  << endl;
    cout << "输出Linked List反转结果" << endl;
    l1.Reverse();
    l1.print();
    
    cout << "***************************"  << endl;
    int search_target = 6;
    cout << "在LinkedList中搜索值为" << search_target << "的节点的位置" << endl;
    l1.Search(search_target);

    cout << "***************************"  << endl;
    int target_position = 3;
    int target_value = 50;
    cout << "设置LinkedList第" << target_position << "位节点的数值为"  << target_value << endl;
    l1.setValueAt(target_position, target_value);
    l1.print();

    cout << "***************************"  << endl;
    target_position = 2;
    cout << "获得LinkedList第" << target_position << "位节点的数值" << endl;
    l1.getValueAt(target_position);

    system("pause");
}

Output

***************************
创建链表开始
输出Linked List创建结果
1 2 3 4 5 6 7 8
***************************
获取链表长度为 8
***************************
插入Linked List!100
输出Linked List插入结果
1 2 3 4 5 6 7 8 100
***************************
删除Linked List 7!
The Deletion Operation had been finished!
输出Linked List删除结果
1 2 3 4 5 6 8 100
***************************
输出Linked List反转结果
100 8 6 5 4 3 2 1
***************************
在LinkedList中搜索值为6的节点的位置
the value you want to search is at position 2
***************************
设置LinkedList第3位节点的数值为50
The Value in this position has been Updated!
100 8 6 50 4 3 2 1
***************************
获得LinkedList第2位节点的数值
In this Position, the vuale is 6

参考连接

C++ 数据结构链表的实现代码主要参考这个

c++ 写一个简单的链表运用了 List.h 头文件，定义了一个链表接口。然后在 List.cpp 源文件中实现了链表点相关的类和方法，运用到了工厂函数。

关键思想总结

1、见到链表就要想到指针，双指针、快慢指针等等。

双指针的奇妙作用
- LeetCode 19. 删除链表的倒数第N个节点（中）：利用双指针间隔进行控制慢指针停下来的位置。
- LeetCode 142. 环形链表 II（中）：检测循环节点位置。
hash map作用
- LeetCode 23，把一个链表操作处理成了排序问题。
- LeetCode 141，把一个链表操作处理成了计数统计问题。

2、保持声明哑结点的好习惯，使用哑结点可以防止特殊情况。 3、链表节点操作（LeetCode 19）、链表合并（LeetCode 23）、链表翻转（LeetCode 24/25/92/206）、循环链表检测（LeetCode 141/142）。 4、特别注意链表翻转类型题目的递归、迭代写法。 5、链表中用hash map解决问题（链表合并/环链表检测），用空间换取时间，如果要优化，可以用指针操作避免使用hash map。

相关题目总结

LeetCode 2. 两数相加（中）

直觉

设立一个表示进位的变量carried，建立一个新链表，把输入的两个链表从头往后同时处理，每两个相加，将结果加上carried后的值作为一个新节点到新链表后面。

关键代码

while l1 or l2:
    x= l1.val if l1 else 0
    y= l2.val if l2 else 0
    s = carry + x + y
    carry = s//10  # 计算进位
    r.next = ListNode(s%10)  # 计算余数
    r = r.next
    if l1 != None:  l1 = l1.next
    if l2 != None:  l2 = l2.next
# 最后还做了个特判
if carry > 0:  r.next=ListNode(1)

题解

LeetCode 2. 两数相加（中）

LeetCode 19. 删除链表的倒数第N个节点（中）

直觉

使用快慢指针，快慢指针间隔为N，使用哑节点处理要删除的节点是第一个节点的情况。

关键代码

for i in range(1, n+1):
    first = first.next
while first.next != None:
    first = first.next
    second = second.next
second.next = second.next.next
return dummy.next

题解

LeetCode-19.-删除链表的倒数第N个节点（中）

LeetCode 23. 合并K个排序链表（难）

直觉

用计数排序的方法或者分治思想来解题。

计数排序：依次遍历统计每个链表中的节点，然后记录val出现的次数到一个hash map中，然后遍历整个hash map依次恢复出一个排好序的链表即可。
分治思想：将合并k个排序链表转化成每次合并 i 个链表，然后递归合并，i += 2 。

关键代码

class Solution(object):
    def mergeKLists(self, lists):
        while interval < amount:
            for i in range(0, amount - interval, interval * 2):
                lists[i] = self.merge2Lists(lists[i], lists[i + interval])  # 重点在于此处划分间隔的方法
            interval *= 2
         # ...

    def merge2Lists(self, l1, l2):
        head = point = ListNode(0)
        while l1 and l2:
            if l1.val <= l2.val:
                point.next = l1
                l1 = l1.next
            else:
                point.next = l2
                l2 = l1  # 这样写保证每次l2都是较大的那个
                l1 = point.next.next
            point = point.next
        # ...

题解

LeetCode-23-合并K个排序链表（难）

LeetCode 24. 两两交换链表中的节点（中）

直觉

基于递归或者迭代实现。

递归：每次递归都负责交换一对节点。下一次递归则是传递的是下一对需要交换的节点。交换了两个节点以后，返回 secondNode，因为它是交换后的新头。在所有节点交换完成以后，我们返回交换后的头，实际上是原始链表的第二个节点

迭代：我们把链表分为两部分，即奇数节点为一部分，偶数节点为一部分，A 指的是交换节点中的前面的节点，B 指的是要交换节点中的后面的节点。在完成它们的交换，我们还得用 prevNode 记录 A 的前驱节点。

关键代码

递归

class Solution(object):
    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

迭代

first_node = head
second_node = head.next

prev_node.next = second_node
first_node.next = second_node.next
second_node.next = first_node

prev_node = first_node
head = first_node.next

题解

LeetCode-24-两两交换链表中的节点（中）

LeetCode 25. K 个一组翻转链（难）

直觉

栈，利用栈先进后出的特点可以做reverse，看到翻转、颠倒一类的名词，就要想到用栈。（线性空间复杂度）

指针，pre -> head -> ... -> tail，固定pre和tail指针，移动cur，将cur所指向的节点依次插到tail后面。

递归，和24题类似，每次递归都负责交换一组节点。下一次递归则是传递的是下一组需要交换的节点。交换了两个节点以后，返回 tail，因为它是交换后的新头。

关键代码

栈

# 将head之后的k个node（包括head本身）入栈
while count and tmp:
    stack.append(tmp)
    tmp = tmp.next
    count -= 1

while stack:
    p.next = stack.pop()
    p = p.next

指针（建议看题解理解过程）

cur = pre.next  # 获取下一个元素 第一个获取的是head.next
pre.next = cur.next  # pre与cur.next连接起来,此时cur(孤单)掉了出来
cur.next = tail.next  # 和剩余的链表连接起来
tail.next = cur  # 插在tail后面

递归

if count == k:
    # 将下一层递归翻转后的head节点作为cur
    cur = self.reverseKGroup(cur, k)
    while count:
        tmp = head.next
        head.next = cur
        cur = head
        head = tmp  
        count -= 1
    head = cur 
return head  # head逐渐后移最终会指向tail

题解

LeetCode 25. K 个一组翻转链（难）

LeetCode 31. 下一个排列（中）

直觉

虽然叫做下一个排列，但是数组加指针来解决，更加简单易于理解。链表用指针比较多，所以放到一起来。

特判：遇到输入序列就是严格降序的，直接返回其升序。如果输入序列不是严格降序，从右往左找到第一对两个连续的数字 a[i] 和 a[i+1]，它们满足 a[i]<a[i+1]（从后往前找）。此时交换这两个数字，就能得到一个比原来序列更大的组合。然后，去a[i+1]右边找到一个a[j]（从后往前找），使得a[j-1]<a[i]<a[j]。这时，交换a[i-1]和a[j]，再对a[i]右边的数字进行一次降序排列，就可以了得到结果了。

关键代码

i = nums_len - 2
while i >= 0 and nums[i+1] <= nums[i]:  # 从后往前找 找一个后面大于前面数字的位置 i
    i -= 1
if i >= 0:
    j = nums_len - 1
    while j >=0 and nums[j] <= nums[i]:  # 从后往前找 找一个比nums[i]要小的位置
        j -= 1
    self.swape(nums, i, j)  # 交换nums[i]和nums[j]
self.reverse(nums, i + 1)

题解

LeetCode 31. 下一个排列（中）

LeetCode 61. 旋转链表（中）

直觉

用快慢指针来解，快指针先走k步，然后两个指针一起走，当快指针走到末尾时，慢指针的位置就是新顺序的尾结点，慢指针的下一个位置是新的顺序的头结点，这样就可以旋转链表了。关键是对输入的 k 进行预处理，我们需要首先遍历一遍原链表得到链表长度n，然后k对n取余，这样k肯定小于n。

关键代码

while p and p.next:
    if p.val == p.next.val:
        p.next = p.next.next
    else:
        p = p.next

题解

LeetCode 61. 旋转链表（中）

LeetCode 83. 删除排序链表中的重复元素（易）

直觉

单指针，相同即跳过，即可去重。

关键代码

while p and p.next:
    if p.val == p.next.val:
        p.next = p.next.next
    else:
        p = p.next

题解

LeetCode-83-删除排序链表中的重复元素（易）

LeetCode 82. 删除排序链表中的重复元素 II（中）

直觉

逐个判断，设置 pre_p 指向出现重复数字之前的一个节点，双指针（快慢）思想。注意利用重复数字做判定的思想。

关键代码

while p and p.next:
    if p.val == p.next.val:  # 出现重复数字
        p.next = p.next.next
        last = p.val
    elif p.val == last:  # 重复数字结束
        pre_p.next = p.next
        p = p.next
        is_pure = False
    else:  # 正常情况
        pre_p = p
        p = p.next
        is_pure = False

题解

LeetCode 82. 删除排序链表中的重复元素 II（中）

LeetCode 86. 分隔链表（中）

直觉

使用 p 指针进行遍历，small 指针跟踪保存较小的那一部分，big 指针跟踪保存较大的那一部分。一次遍历结束之后，将 small 和 big 拼接返回即可，注意，由于可能出现数字0，所以判断 small 或 big 部分非空的条件不是 if samll.val 而是 small.val != None。

关键代码

while p:
    if p.val < x:
        small.next = p
        small = small.next
    else:
        big.next = p
        big = big.next
    p = p.next

题解

LeetCode 86. 分隔链表（中）

LeetCode 92. 反转链表 II（中）

直觉

栈和指针：链表反转，没有空间复杂度要求的时候，都可以考虑用栈结合指针处理。

指针：设置哑结点，直接从第一个遍历到最后一个，在需要翻转的区间内两两交换即可。

关键代码

栈和指针

cur = dummy
stack = list()

while m != 1:
    cur = cur.next
    m -= 1
pre_p = cur

while count > -1:
    cur = cur.next
    stack.append(cur)
    count -= 1

tail = cur.next
while True:
    pre_p.next = stack.pop()
    pre_p = pre_p.next
    if stack == []:
        break
pre_p.next = tail

指针

while count <= n + 1:
    if count < m: # 还未达到开始位置
        p = p.next
        pre_p = pre_p.next
    elif count == m:  # 到达开始位置，固定pre_start。
        pre_start = pre_p  # start指针的前指针
        start = p  # start指针
        p = p.next
        pre_p = pre_p.next
    elif m < count <= n:  # 超过开始翻转 两两交换
        next_p = p.next  # 保留下一个位置
        cur_p = p  # 保留当前位置
        p.next = pre_p  # 当前节点断开与后续节点的链接，反向链接前一个节点。  
        p = next_p  # p指针依靠next_p向后移动
        pre_p = cur_p  # pre_p依靠cur_p指针向后移动
    else:  # 超过结束位置 count > n
        pre_start.next = pre_p  # pre_start所指节点指向扫描末尾的节点，pre_start所指节点成为了翻转之后的头节点。
        start.next = p # start所指节点指向未翻转部分的节点，start所指节点成为了翻转之后的尾节点。
    count += 1  # count 增加

题解

LeetCode 92. 反转链表 II（中）

LeetCode 141. 环形链表（易）

直觉

hash map：通过检查一个结点此前是否被访问过来判断链表是否为环形链表

快慢指针：通过使用具有不同速度的快、慢两个指针遍历链表，空间复杂度可以被降低至 O(1)。慢指针每次移动一步，而快指针每次移动两步。如果列表中不存在环，最终快指针将会最先到达尾部，此时我们可以返回 false。如果存在环，则最终两个指针会相遇。

关键代码

hash map

nodesSeen = list()
while head:
    # 这里不能用Value(head.val)做判断，而要用ListNode(head)做判断。
    if head in nodesSeen:
	    return True
    else:
    	nodesSeen.append(head)
    head = head.next
return False

快慢指针

while slow != fast:
    if fast == None or fast.next == None:  # 这一点很关键
	    return False
    slow = slow.next
    fast = fast.next.next

题解

LeetCode 141. 环形链表（易）

LeetCode 142. 环形链表 II（中）

直觉

hash map：基于hash表检查第一个之前就被访问过的节点，将其返回。

Folyd算法：第一阶段、找到相遇点。第二阶段、初始化额外的两个指针： ptr1 ，指向链表的头（下图中的 list head）， ptr2 指向相遇点（下图中的 first interaction）。然后，我们每次将它们往前移动一步，直到它们相遇，它们相遇的点就是环的入口，返回这个节点。

关键代码

hash map

nodesSee = list()
while head:
    if head in nodesSee:
        return head
    else:
        nodesSee.append(head)
    head = head.next

Folyd算法

# 第一阶段
while fast != None and fast.next != None:
    slow = slow.next
    fast = fast.next.next
    if slow == fast:
        return slow

# 第二阶段
ptr1 = head
ptr2 = encounter
while ptr1 != ptr2:
    ptr1 = ptr1.next
    ptr2 = ptr2.next
return ptr1

题解

LeetCode 142. 环形链表 II（中）

LeetCode 146. LRU缓存机制（中）

直觉

哈希表保存key-value，链表保存使用时间前后关系。新插入或者刚刚访问过的key，放到双向链表最前面，如果新插入时cache容量不够，就删除双向链表最后面的那个节点（最近最久未使用）。

关键代码

# 定义双链表节点
class DLinkedNode():
    """bidirectional linked list
    """
    def __init__(self):
        self.key = 0
        self.val = 0
        self.prev = None
        self.next = None

# 定义LRU Cache类，有添加节点、删除节点、移动到链表开头、移动到链表结尾、删除链表尾结点、初始化、get函数 
class LRUCache():

    def __init__(self, capacity):
        self.cache = {}  # hash map负责保存DLinkedNode，双向链表负责保存使用时间。
        self.size = 0  # 保存当前已经存储的缓存数量
        self.capacity = capacity  # 保存该LRUCache能够保存的最多缓存数量
        self.head, self.tail = DLinkedNode(), DLinkedNode()  # head和tail起哑节点的作用
        self.head.next = self.tail
        self.tail.prev = self.head

    def addNode(self, node):
        """Always add the new node at the front of linkedlist
        """
        node.prev = self.head
        node.next = self.head.next

        self.head.next.prev = node
        self.head.next = node
    
    def removeNode(self, node):
        """Remove an existing node from the linked list
        """
        prev = node.prev
        new = node.next

        prev.next = new
        new.prev = prev
    
    def moveToHead(self, node):
        """Move certian node to head
        """
        self.removeNode(node)  # 先删除
        self.addNode(node)  # 后添加

    def popTailNode(self):
        """pop tail node in the DLinkedList
        """
        _node = self.tail.prev
        self.removeNode(_node)
        return _node

题解

LeetCode 146. LRU缓存机制（中）

LeetCode 206. 反转链表（易）

直觉

循环：更新 pre_p、p、next_p 四个指针，设置哑节点，每次把要反转的 p 节点指向 pre_p ，先利用 p 更新 pre_p，再利用 next_p 更新 p 。

递归：是从后往前递归的，假设后面一部分已经反转好，现在要反转前面一部分。递归的最后一层就是 tail，tail 被逐层 return。

关键代码

循环

while p:                                             # 7
    next_p = p.next                                  # 8
    p.next = pre_p                                   # 9
    pre_p = p                                        # 10
    p = next_p                                       # 11
    head.next = None                                 # 12

递归

1
2
3

p = self.reverseList(head.next)                     # 3
head.next.next = head                               # 4
head.next = None                                    # 5

题解

LeetCode 206. 反转链表

算法与数据结构

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

LeetCode 141. 环形链表（易）上一篇

2016年总统竞选时特朗普的葛底斯堡演讲下一篇

数据结构：链表

Python3 单向链表基础代码

声明链表节点

创建链表

逐个输出链表节点

获取链表长度

插入ListNode

删除ListNode

链表反转

LinkedList 转Python List

主函数

C++ 单向链表基础代码

声明链表节点

声明LinkedList结构

创建链表

逐个输出链表节点

获取链表长度

插入ListNode

删除ListNode

链表反转

搜索链表

获取特定节点上的值

设置特定节点上的值

主函数

关键思想总结

相关题目总结

LeetCode 2. 两数相加（中）

LeetCode 19. 删除链表的倒数第N个节点（中）

LeetCode 23. 合并K个排序链表（难）

LeetCode 24. 两两交换链表中的节点（中）

LeetCode 25. K 个一组翻转链（难）

LeetCode 31. 下一个排列（中）

LeetCode 61. 旋转链表（中）

LeetCode 83. 删除排序链表中的重复元素（易）

LeetCode 82. 删除排序链表中的重复元素 II（中）

LeetCode 86. 分隔链表（中）

LeetCode 92. 反转链表 II（中）

LeetCode 141. 环形链表（易）

LeetCode 142. 环形链表 II（中）

LeetCode 146. LRU缓存机制（中）

LeetCode 206. 反转链表（易）