链表核心概念与经典算法题解析

链表核心概念与经典算法题解析

一、前言

接下来进入基础数据结构部分。

二、链表

2.1 本质

链表就是把数据离散开。

2.2 误区

头结点：不存任何数据
首元结点：存放着第一个数据

2.3 思路

• 根据题意选择合适的链表类型，如：单链表（带或不带头节点）
• 模拟遍历或快慢指针思想

2.4 题型

2.4.1 LeetCode

• 206. 反转链表（头插法）两种思路：
  • 头插法：p = q; q = p->next; p->next = NULL; 从第一个节点开始，挨个摘下每一个节点，摘下后用头插法建立新的链表

142. 环形链表 II题意：判断有没有环以及从哪个节点开始进入环的（类似于跑步套圈的情况）。思路：如果有环，总有一天快指针会和慢指针相遇，并且快慢指针永远不会跑到空的地方；如果没环，快指针会很快指向空的地方。如何看从哪里开始进入环呢？快慢指针：快慢指针相遇一定是在圈里相遇。假设相遇点是 x，f 指针走的快，先绕圈；s 指针走的慢，后开始绕圈。f 指针走了 a + b，继续走；s 指针先走了 a，进入圈刚走了 b 就和 f 指针相遇了。此时，f 已经跑了 n 圈，a + n * (b + c) + b。如图：

快指针和慢指针走，当它们两个相遇的时候，快指针就停下来，在用一个慢指针从起点开始走，慢指针继续走，当第一个慢指针又和第二个慢指针相遇的时候，就是开始进入圈的点。代码：

// 判断成环
#include <iostream>
#include <algorithm>
using namespace std;

typedef struct ListNode {
    int val;
    ListNode *next;
} ListNode;

ListNode*  {
    ListNode* f = head;
    ListNode* s = head;
     (f != ) {
        s = s->next;
         (f->next == ) {
             ;
        }
        f = f->next->next;
         (s == f) {
            ListNode* p = head;
             (p != s) {
                p = p->next;
                s = s->next;
            }
             p;
        }
    }
     ;
}

{
     n, x;
    
    cin >> n;
    ListNode* head = ;
    ListNode* r = ;
     ( i = ; i <= n; i++) {
        cin >> x;
        ListNode* s = (ListNode*)((ListNode));
        s->val = x;
        s->next = ;
         (i == ) {
            head = s;
            r = s;
        }  {
            
            r->next = s;
            r = s;
        }
    }
    cin >> x;
    ListNode* ans = (head);
     (ans == ) {
        cout <<  << endl;
    }  {
        cout << ans->val << endl;
    }
     ;
}