Rhythmli's blog
梁山话事人
最新推荐文章2025-08-13
目录

leetcode01--链表

原文链接：https://blog.csdn.net/qq_39355828/article/details/113729084 (opens new window)

# leetcode刷题01–链表

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。

#include <iostream>
struct ListNode
{
   int val;//数据区域
   ListNode *next;//存储下一个指针位置
};
int main() {
   ListNode a;//定义节点
   ListNode b;
   ListNode c;
   ListNode d;
   ListNode e;
   printf("%d\n",sizeof(a.next));
   printf("%d\n",sizeof(a.val));
   printf("%d\n",sizeof(a));
   a.val=10;//节点赋值
   b.val=20;
   c.val=40;
   d.val=50;
   a.next=&b;//a的下一个位置是b;节点链接
   b.next=&c;
   c.next=&d;
   d.next=&e;
   e.next=NULL;
   ListNode *head=&a;
   while(head)//节点遍历
   {
       printf("%d\n",head->val);
       head=head->next;
   }
   return 0;
}
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

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-JhxIo7WG-1612607331693)(C:\Users\lhh31\AppData\Roaming\Typora\typora-user-images\1611901644714.png)]

问题发现： int是8个字节，指针是4个字节，但一个节点大小却有16个字节。中间少的四个字节用作对齐字节。

# 例1.反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 进阶: 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/reverse-linked-list 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：遍历链表，设置一个新链表，每取一个链表中的元素，指针都指向新链表，循环一次实现反转。

#include <iostream>
struct ListNode
{
    int val;//数据区域
    ListNode *next;//存储下一个指针位置
    ListNode(int x):val(x),next(NULL){}
};
class Solution
        {
        public:
            ListNode* resverseList(ListNode* head){
            ListNode *new_head=NULL;
            while(head)
            {
                ListNode *next=head->next;//备份head->next
                head->next=new_head;//更新head->next
                new_head=head;//移动head->next
                head=next;//移动new_head
            }
            return new_head;
            }
        };
int main() {
    ListNode a(1);//建立节点
    ListNode b(2);
    ListNode c(3);
    ListNode d(4);
    ListNode e(5);
    a.next=&b;//将节点简单链接在一起
    b.next=&c;
    c.next=&d;
    d.next=&e;
    Solution solve;
    ListNode *head=&a;//加上头节点
    printf("Before reverse:\n");
    while(head)//顺序输出链表
    {
        printf("%d      ",head->val);
        head=head->next;
    }
    head=solve.resverseList(&a);
    printf("After reverse:\n");
    while(head) {
        printf("%d      ",head->val);
        head = head->next;
    }
    return 0;
}
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

# 例2.反转从位置 m 到 n 的链表。

请使用一趟扫描完成反转。说明: 1 ≤ m ≤ n ≤ 链表长度。

示例:

输入: 1->2->3->4->5->NULL, m = 2, n = 4 输出: 1->4->3->2->5->NULL

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/reverse-linked-list-ii 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

先定位到反转部分开始地方，m–，然后开始反转，反转长度到changelen，反转结束后，接上头和尾

#include<iostream>
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* reverseBetween(ListNode* head,int m,int n)
    {
        int change_len=n-m+1;//计算需要逆置的节点个数
        ListNode *pre_head=NULL;//初始化开始逆置的节点的前驱
        ListNode *result=head;//最终转换后的链表头节点，
        while(head&&--m)//将head向前移动m-1个位置
        {
            pre_head=head;
            head=head->next;
        }
        //将modify_list_tail指向当前的head,
        ListNode *modify_list_tail=head;
        ListNode *new_head=NULL;
        while (head&&change_len)
        {
           ListNode *next=head->next;
           new_head=head;
           head=next;
           change_len--;
        }
        modify_list_tail->next=head;
        if(pre_head)
        {
            pre_head->next=new_head;
        }
        else
        {
            result=new_head;
        }
        return result;
    }
};
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

# 例3. 相交链表

编写一个程序，找到两个单链表相交的起始节点。

如下面的两个链表**：**

img (opens new window)

在节点 c1 开始相交。

https://assets.leetcode.com/uploads/2018/12/13/160_example_1.png)

预备知识

STL中set使用:判断集合中是否存在某个元素

#include<iostream>
#include<set>
using namespace std;
/*struct ListNode
{
    int val;
    ListNode *next;
    ListNode(int x):val(x),next(NULL)
    {}//构造函数
};
class Solution
{
public:
    ListNode *getIntersectionNode(ListNode *headA,ListNode *headB)
    {

    }
};*/
int main()
{
    set<int>test_set;
    const int ALen=7;
    const int Blen=8;
    int a[ALen]={5,1,4,8,10,1,3};
    int b[Blen]={2,7,6,3,1,6,0,1};
    for(int i=0;i<ALen;i++)
    {
        test_set.insert(a[i]);
    }
    for(int i=0;i<Blen;i++)
    {
        if(test_set.find(b[i])!=test_set.end())
        {
           printf("b[%d]= %d in array A.\n",i,b[i]);
        }
    }
    return 0;
}
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

1.遍历链表A，将A中的指针地址，写入set 2.遍历链表B，将B中节点对应的指针地址，在set中查找，发现在set中的第一个节点地址，即是两个链表交点。

#include<iostream>
#include<set>
using namespace std;
struct ListNode
{
    int val;
    ListNode *next;
    ListNode(int x):val(x),next(NULL)
    {}//构造函数
};
class Solution
{
public:
    ListNode *getIntersectionNode(ListNode *headA,ListNode *headB)
    {
       set<ListNode*>node_set;
       while(headA)
       {
           node_set.insert(headA);
           headA=headA->next;
       }
       while(headB)
       {
           if(node_set.find(headB)!=node_set.end())
           {
               return headB;
           }
           headB=headB->next;
       }
       return NULL;
    }
};
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

# 例4.链表求环

给定一个链表，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。 否则，返回 false 。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/linked-list-cycle 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

1.遍历链表，将链表中节点对应的指针地址从插入set 2.在插入前，在set中寻找，第一个set中发现的节点地址，就是链表环的起点。

struct ListNode
{
    int val;
    ListNode* next;
};
class Solution
{
public:
    ListNode *detectCycle(ListNode *head)
    {
        set<ListNode*>node_set;
        while(head)
        {
            if(node_set.find(head)!=node_set.end())
            {
                return head;
            }
            node_set.insert(head);
            head=head->next;
        }
        return NULL;//
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# 例5.链表划分

给你一个链表和一个特定值 x ，请你对链表进行分隔，使得所有小于 x 的节点都出现在大于或等于 x 的节点之前。

你应当保留两个分区中每个节点的初始相对位置。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/partition-list 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#include<iostream>
using namespace std;
     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* partition(ListNode* head, int x) {
        ListNode less_head(0);
        ListNode more_head(0);
        ListNode *lessptr=&less_head;
        ListNode* moreptr=&more_head;
     while(head)
     {
        if(head->val<x)
        {
            lessptr->next=head;//将下一个加到队尾
            lessptr=head;//指针向后移动
        }
        else
        {
            more_head.next=head;
            moreptr=head;
        }
            head=head->next;
     }
     lessptr->next=more_head.next;
     moreptr->next=NULL;
     return less_head.next;
    }
};
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

# 例6.合并有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

先比较两个链表中数值的大小，当其中一个结束时候，直接将另一个加到后面。

#include<iostream>
using namespace std;
     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* mergeTwoLists(ListNode *L1,ListNode * L2)
    {
        ListNode temp_head(0);
        ListNode *pre=&temp_head;
        while(L1&&L2)
        {
            if(L1->val<L2->val)
            {
                pre->next=L1;
                L1=L1->next;
            }
            else
            {
                pre->next=L2;
                L2=L2->next;
            }
            pre=pre->next;//pre指向新连接的节点
        }
        if(L1)//L1还没有结束
        {
            pre->next=L1;
        }
        if(L2)
        {
            pre->next=L2;
        }
        return temp_head.next;
    }
};
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
编辑 (opens new window)
#leetcode刷题#订阅专栏#查看详情#C++
上次更新: 2026/08/11, 13:36:18
leetcode03_贪心算法
leetcode_02栈

← leetcode_02栈→

最近更新
01
Spring IOC
03-31
02
Git修改分支名
08-11
03
CSS给table的tbody添加滚动条
06-29
更多文章>
Theme by Vdoing | Copyright © 2019-2026 Evan Xu | MIT License