本站消息

站长简介/公众号

出租广告位,需要合作请联系站长

黎明要到来了

1031

文章

844712

访问

+关注

分类

暂无分类

日期归档

2023-05(1)

2023-06(1)

算法 64式 9、链表算法整理

发布于2019-08-21 10:04 阅读(1450) 评论(0) 点赞(15) 收藏(3)

1算法思想

链表

1.1含义

线性表:具有相同数据类型的n个数据元素的有限序列

单链表:线性表的链式存储，通过一组任意的存储单元来存储线性表中的元素。

链表结点:包含数据域存放数据元素，next指针域存放后继结点的地址

类型描述如下:

Typedef struct LNode{

ElemType data; //数据域

struct LNode *next; // 指针域

}LNode, *LinkList;

1.2特点

优点:解决顺序表需要大量连续存储空间的缺点

缺点:指针域会浪费存储空间

1.3适用

不需要使用地址连续的存储单元

1.4通用解法

链表算法:

1 给链表加入一个头结点往往能简化问题

2 插入、删除链表中的元素时，需要注意可能需要事先将链表当前需要处理结点的前一个结点的保存下来

3 处理链表问题，关键就是处理好结点之间的指向关系

1.5经典例题讲解

如何合并两个有序链表

已知两个链表head1和head2各自有序(例如升序排序)，请把它们合并成一个链表，

要求合并后的链表仍然有序。

分析

情况1:

curr1.data > curr2.data,则

说明curr2应该插入到curr1结点的前一个结点的位置，则执行:

curr2.nextNode = curr1

prev1.nextNode = curr2

注意: 需要将prev1设置为新插入的curr2,否则出错

prev1 = curr2

并且curr2应该继续向下走

curr2 = next2

next2 = next2.nextNode if next2 else None

情况2:

curr1.data <= curr2.data, 则

prev1 = curr1

curr1 = next1

next1 = next1.nextNode if next1 else None

说明curr1需要继续遍历，直到curr1.data大于curr2.data，

然后重复情况1的步骤

如果最后curr2不为空，则

prev1.nextNode = curr2

代码如下

def mergeList(head1, head2):

if not head1 and not head2:

return

elif not head1:

return head2

elif not head2:

return head1

prev1 = head1

curr1 = head1.nextNode

next1 = curr1.nextNode if curr1 else None

prev2 = head2

curr2 = head2.nextNode

next2 = curr2.nextNode if curr2 else None

while curr1 and curr2:

if curr1.data > curr2.data:

curr2.nextNode = curr1

prev1.nextNode = curr2

# 注意，这里prev1也要更新为curr2

prev1 = curr2

prev2 = curr2

curr2 = next2

next2 = next2.nextNode if next2 else None

else:

prev1 = curr1

curr1 = next1

next1 = next1.nextNode if next1 else None

# 链表2不为空，链表1为空，说明链表2剩余结点的值都大于链表1的最后一个结点

# 链表1需要接上链表2

if curr2:

prev1.nextNode = curr2

return head1

2 链表系列

类别-编号	题目	遁去的1	来源
1	从尾到头打印链表输入一个链表的头结点，从尾到头反过来打印出每个节点的值		剑指offer https://blog.csdn.net/qingyuanluofeng/article/details/39092187
2	在O(1)时间删除链表节点: 给定单向链表的头指针和一个结点指针，定义一个函数在O(1)时间删除该节点。链表结点与函数的定义如下		剑指offer https://blog.csdn.net/qingyuanluofeng/article/details/39138121
3	链表中倒数第k个节点: 输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第一个节点。例如一个链表有6个节点，从头节点开始它们的值依次是1，2，3，4，5，6。这个链表的倒数第三个节点是值为4的结点。		剑指offer https://blog.csdn.net/qingyuanluofeng/article/details/39138143
4	反转链表定义一个函数，输入一个链表的头结点，反转该链表并输出翻转后链表的头结点。		剑指offer https://blog.csdn.net/qingyuanluofeng/article/details/39138155
5	合并两个排序的链表输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是按照递增排序的。例如输入图中的链表1和链表2，则合并之后的升序链表入链表3所示		剑指offer https://blog.csdn.net/qingyuanluofeng/article/details/39138171
6	复杂链表的复制: 请事先函数ComplexListNode* Clone(ComplexListNode* pHead)，复制一个复杂链表。在复杂链表中，每个结点除了有一个m_pNext指针指向下一个结点外，还有一个m_pSibling指向链表中的任意结点或者NULL。 A->B->C->D->E 兄弟指向" A指向C B指向E D指向B E,C指向NUL		剑指offer https://blog.csdn.net/qingyuanluofeng/article/details/39138361
7	二叉搜索树与双向链表: 输入一颗二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中节点指针的指向。比如，输入图中左边的二叉搜索树，则输出转换之后的排序双向链表。 10 6 14 4 812 16 转换为: 4->6->8->10->12->14->16 <- <- <- <- <- <-		剑指offer https://blog.csdn.net/qingyuanluofeng/article/details/39138375
8	两个链表的第一个公共结点: 输入两个链表，找出它们的第一个公共结点。		剑指offer https://blog.csdn.net/qingyuanluofeng/article/details/39187861
9	从无头单链表中删除节点假设有一个没有头指针的单链表。一个指针指向此单链表中间的某一个节点(不是第一个，也不是最后一个)，请将该节点从单链表中删除		编程之美 https://blog.csdn.net/qingyuanluofeng/article/details/47187597
10	编程判断两个链表是否交叉:(本质判断两个链表是否有公共结点) 给出两个单向链表的头指针，如h1,h2,判断这两个链表是相交。假设两个链表均不带环。 h1->->-> ->->->...->NULL h2->->->		编程之美 https://blog.csdn.net/qingyuanluofeng/article/details/47187635
11	移除未排序链表中重复的节点编写代码，移除未排序链表中的重复节点		程序员面试金典 https://blog.csdn.net/qingyuanluofeng/article/details/53780547
12	找出单向链表中倒数第k个节点实现一个算法，找出单项链表中倒数第k个结点		程序员面试金典 https://blog.csdn.net/qingyuanluofeng/article/details/53780983
13	想像有个Web服务器，实现简化版搜索引擎。这套系统有100台机器来响应搜索查询，可能会对另外的机器集群调用processSearch(string query)以得到真正的结果。响应查询请求的机器是随机挑选的，因此两个同样地请求不一定由同一台机器响应。方法processSearch的开销很大，请设计一种缓存机制，缓存最近几次查询的结果。当数据发生变化时，务必说明该如何更新缓存。		程序员面试金典 https://blog.csdn.net/qingyuanluofeng/article/details/54348791
14	以给定值x为基准将链表分割成两部分以给定值x为基准将链表分隔成两部分，所有小于x的结点排在大于或等于x的结点之前		程序员面试金典 https://blog.csdn.net/qingyuanluofeng/article/details/53783044
15	对两个用链表表示的整数求和给定两个用链表表示的整数，每个节点包含一个数位。这些数位是反向存放的，也就是个位排在链表首部。编写函数对这两个整数求和，并用链表形式返回结果。		程序员面试金典 https://blog.csdn.net/qingyuanluofeng/article/details/53784998
16	给定有环链表，实现算法返回环路的开头节点		程序员面试金典 https://blog.csdn.net/qingyuanluofeng/article/details/53787230
17	检查链表是否为回文编写一个函数，检查链表是否为回文		程序员面试金典 https://blog.csdn.net/qingyuanluofeng/article/details/53787704
18	Remove Nth Node From End of List Given a linked list, remove the nth node from the end of list and return its head. For example, Given linked list: 1->2->3->4->5, and n = 2. After removing the second node from the end, the linked list becomes 1->2->3->5. Note: Given n will always be valid. Try to do this in one pass. 翻译: 这个是删除链表倒数第n个结点。		Leecode https://blog.csdn.net/qingyuanluofeng/article/details/54799052
19	Merge Two Sorted Lists Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.		Leecode https://blog.csdn.net/qingyuanluofeng/article/details/54799851
20	Swap Nodes in Pairs Given a linked list, swap every two adjacent nodes and return its head. For example, Given 1->2->3->4, you should return the list as 2->1->4->3. Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed. 分析:交换链表中相邻两个结点，并且不是结点中的值交换。而且只能使用常量空间。		Leecode https://blog.csdn.net/qingyuanluofeng/article/details/54808155
21	Reverse Nodes in k-Group Given a linked list, reverse the nodes of a linked list k at a time and return its modified list. k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is. You may not alter the values in the nodes, only nodes itself may be changed. Only constant memory is allowed. For example, Given this linked list: 1->2->3->4->5 For k = 2, you should return: 2->1->4->3->5 For k = 3, you should return: 3->2->1->4->5 分析: a multiple of k:k的倍数注意：k的倍数内的结点反转，剩余的部分保持不变。因此有点类似于: 1~k反转，k+1~2k反转。那就需要将结点分成长度为k的组，每一组组内反转，除了首结点没有前驱外，其余结点找到前驱结点，令当前结点指向前驱结点即可。关键只允许常量空间		Leecode https://blog.csdn.net/qingyuanluofeng/article/details/54808155
22	Rotate List Given a list, rotate the list to the right by k places, where k is non-negative. For example: Given 1->2->3->4->5->NULL and k = 2, return 4->5->1->2->3->NULL. 分析:题目的意思应该是将链表最右侧的结点转转到最左边，重复这样的操作k次。此题可以等效替换成寻找到倒数第k个结点，		Leecode https://blog.csdn.net/qingyuanluofeng/article/details/54980834
23	Remove Duplicates from Sorted List II Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. For example, Given 1->2->3->3->4->4->5, return 1->2->5. Given 1->1->1->2->3, return 2->3. 分析:这道题目实际上就是要删除所有重复元素对应的所有节点。		Leecode https://blog.csdn.net/qingyuanluofeng/article/details/55008663
24	Remove Duplicates from Sorted List Given a sorted linked list, delete all duplicates such that each element appear only once. For example, Given 1->1->2, return 1->2. Given 1->1->2->3->3, return 1->2->3. 分析:删除链表中的冗余元素，多个元素只保留一个。		Leecode https://blog.csdn.net/qingyuanluofeng/article/details/55012234
25	Partition List Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x. You should preserve the original relative order of the nodes in each of the two partitions. For example, Given 1->4->3->2->5->2 and x = 3, return 1->2->2->4->3->5. 分析:题目给定一个链表和一个值，用该值进行划分，所有小于该值的数都出现在大于等于该值的数的前面，而且需要保持两个划分中相对顺序不能改变		Leecode https://blog.csdn.net/qingyuanluofeng/article/details/55049549
26	Reverse Linked List II Reverse a linked list from position m to n. Do it in-place and in one-pass. For example: Given 1->2->3->4->5->NULL, m = 2 and n = 4, return 1->4->3->2->5->NULL. Note: Given m, n satisfy the following condition: 1 ≤ m ≤ n ≤ length of list. 分析:逆置指定两个位置及其中间的结点。		Leecode https://blog.csdn.net/qingyuanluofeng/article/details/55061701
27	Copy List with Random Pointer A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null. Return a deep copy of the list.		Leecode https://blog.csdn.net/qingyuanluofeng/article/details/55667027
28	Linked List Cycle Given a linked list, determine if it has a cycle in it. Follow up: Can you solve it without using extra space? 分析:分析一个链表是否有环，		Leecode https://blog.csdn.net/qingyuanluofeng/article/details/55668626
29	Linked List Cycle II Given a linked list, return the node where the cycle begins. If there is no cycle, return null. Note: Do not modify the linked list. Follow up: Can you solve it without using extra space? 分析:给定一个链表，返回环开始的那个节点，如果没有环，返回空。不要修改链表。		Leecode https://blog.csdn.net/qingyuanluofeng/article/details/55669703
30	Reorder List Given a singly linked list L: L0→L1→…→Ln-1→Ln, reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→… You must do this in-place without altering the nodes' values. For example, Given {1,2,3,4}, reorder it to {1,4,2,3}. 分析:此题就是要将最后面的结点插在第一个结点后面，倒数第二个结点插在第二个结点后面且不允许修改结点的值。		Leecode https://blog.csdn.net/qingyuanluofeng/article/details/55669966
31	LRU Cache Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put. get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1. put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item. Follow up: Could you do both operations in O(1) time complexity? Example: LRUCache cache = new LRUCache( 2 capacity ); 分析:最近最少使用缓存。题目要求能够将最近最不经常使用的元素能够在缓存超出容量的条件下在O(1)时间内删除，如果缓存不存在，那么插入缓存：耗费的时间也是O(1)。		Leecode https://blog.csdn.net/qingyuanluofeng/article/details/55706176
32	Insertion Sort List Sort a linked list using insertion sort. 分析:用插入排序对一个链表排序。		Leecode https://blog.csdn.net/qingyuanluofeng/article/details/55790432
33	Sort List Sort a linked list in O(n log n) time using constant space complexity. 分析：在O(NlogN)时间内使用常量空间对一个链表排序		Leecode https://blog.csdn.net/qingyuanluofeng/article/details/56016376
34	Intersection of Two Linked Lists Write a program to find the node at which the intersection of two singly linked lists begins. For example, the following two linked lists: A: a1 → a2 ↘ c1 → c2 → c3 ↗ B: b1 → b2 → b3 begin to intersect at node c1. Notes: If the two linked lists have no intersection at all, return null. The linked lists must retain their original structure after the function returns. You may assume there are no cycles anywhere in the entire linked structure. Your code should preferably run in O(n) time and use only O(1) memory. Credits: Special thanks to @stellari for adding this problem and creating all test cases. 分析:写一个程序，判断两个链表交叉处的第一个结点，如果没有交叉，返回NULL。不能改变原有结构必须在O(n)时间内完成，使用O(1)的空间。		Leecode https://blog.csdn.net/qingyuanluofeng/article/details/56039127
35	Remove Linked List Elements Remove all elements from a linked list of integers that have value val. Example Given: 1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6, val = 6 Return: 1 --> 2 --> 3 --> 4 --> 5 分析:删除链表中等于指定元素的所有结点。		Leecode https://blog.csdn.net/qingyuanluofeng/article/details/56329681
36	Reverse Linked List Reverse a singly linked list. click to show more hints. Hint: A linked list can be reversed either iteratively or recursively. Could you implement both? 分析:逆置一个单链表。最好能迭代逆置或递归逆置。		Leecode https://blog.csdn.net/qingyuanluofeng/article/details/56480559
37	Palindrome Linked List Given a singly linked list, determine if it is a palindrome. Follow up: Could you do it in O(n) time and O(1) space? 分析:给定单链表，能否在O(n)时间和O(1)空间确定其是否是回文的。		Leecode https://blog.csdn.net/qingyuanluofeng/article/details/56695581
38	Delete Node in a Linked List Write a function to delete a node (except the tail) in a singly linked list, given only access to that node. Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with value 3, the linked list should become 1 -> 2 -> 4 after calling your function. 分析:此题是给定一个结点(不是尾结点)，要删除该结点		Leecode https://blog.csdn.net/qingyuanluofeng/article/details/56842646
39	Odd Even Linked List Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes. You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity. Example: Given 1->2->3->4->5->NULL, return 1->3->5->2->4->NULL. Note: The relative order inside both the even and odd groups should remain as it was in the input. The first node is considered odd, the second node even and so on ... 分析:题目要求将所有偶数的结点放置在所有奇数结点的后面，并且偶数结点和奇数结点本身各自维持自己的相对顺序不变。在常量空间复杂度和线性时间复杂度下求解。		Leecode https://blog.csdn.net/qingyuanluofeng/article/details/59038740
40	如何实现链表的逆序给定一个带头结点的单链表，请将其逆序，即如果单链表原来为: head->1->2->3->4->5->6->7，那么逆序后变为 head->7->6->5->4->3->2->1		Python程序员面试算法宝典 https://blog.csdn.net/qingyuanluofeng/article/details/89305686
41	如何从无序链表中移除重复项给定一个没有排序的链表，去掉其重复项，并保留原顺序，例如链表 1->3->1->5->5->7，去掉重复项后变为1->3->5->7		Python程序员面试算法宝典 https://blog.csdn.net/qingyuanluofeng/article/details/89325898
42	如何计算两个单链表所代表的数之和给定两个单链表，链表的每个节点代表一位数，计算两个数的和。例如: 输入链表(3->1->5)和链表(5->9->2)，输出: 8->0->8，即513+295=808，注意个位数在链表头		Python程序员面试算法宝典 https://blog.csdn.net/qingyuanluofeng/article/details/89348759
43	如何对链表进行重新排序给定链表L0->L1->...Ln-1->Ln，把链表重新排序为L0->Ln->L1->Ln-1->L2->Ln-2...。要求: (1) 在原来链表的基础上进行排序，即不能申请新的结点； (2) 只能修改结点的next域，不能修改数据域。		Python程序员面试算法宝典 https://blog.csdn.net/qingyuanluofeng/article/details/89393090
44	如何找出单链表中的倒数第k个元素找出单链表中的倒数低k个元素，例如给定单链表: 1->2->3->4->5->6->7,则单链表的倒数第k=3个元素为5		Python程序员面试算法宝典 https://blog.csdn.net/qingyuanluofeng/article/details/89630808
45	如何检测一个较大的单链表是否有环单链表有环指的是单链表中某个结点的next域指向的是链表中在它之前的某一个结点，这样在链表的尾部形成一个环形结构。如何判断单链表是否有环存在		Python程序员面试算法宝典 https://blog.csdn.net/qingyuanluofeng/article/details/89668102
46	如何把链表相邻元素翻转把链表相邻元素翻转，例如给定链表为 1->2->3->4->5->6->7，则翻转后的链表变为 2->1->4->3->6->5->7		Python程序员面试算法宝典 https://blog.csdn.net/qingyuanluofeng/article/details/89873662
47	如何把链表以K个节点为一组进行翻转 K链表翻转是指把每K个相邻的结点看成一组进行翻转，如果剩余结点不足K个，则保持不变。假设给定链表1->2->3->4->5->6->7和一个数K，如果K的值为2，那么翻转后的链表为 2->1->4->3->6->5->7。如果K的值为3，那么翻转后的链表为: 3->2->1->6->5->4->7。		Python程序员面试算法宝典 https://blog.csdn.net/qingyuanluofeng/article/details/89930863
48	如何合并两个有序链表已知两个链表head1和head2各自有序(例如升序排序)，请把它们合并成一个链表，要求合并后的链表仍然有序。		Python程序员面试算法宝典 https://blog.csdn.net/qingyuanluofeng/article/details/89944625
49	如何在只给定单链表中某个结点的指针的情况下删除该结点假设给定链表1->2->3->4->5->6->7中指向第5个元素的指针，要求把结点5删掉，删除后链表变为 1->2->3->4->6->7。		Python程序员面试算法宝典 https://blog.csdn.net/qingyuanluofeng/article/details/89944687
50	如何判断两个链表(无环)是否交叉单链表相交指的是两个链表存在完全重合的部分，如下图所示: head1->1->2->3->4->5->6->7 head2->1->2->3->4 在上图中，这两个链表相交于结点5，要求判断两个链表是否相交，如果相交，找出相交处的结点。		Python程序员面试算法宝典 https://blog.csdn.net/qingyuanluofeng/article/details/90109288
51	如何展开链接列表给定一个有序链表，其中每个节点也表示一个有序链表，结点包含两个类型的指针: (1) 指向主链表中下一个结点的指针(在下面的代码中称为正确指针) (2) 指向此结点头的链表(在下面的代码中称为down指针) 所有链表都被排序。请参见以下示例: 3 -> 11 -> 15 -> 30 \|V \|V \|V \|V 6 21 22 39 \|V \|V \|V 8 50 40 \|V \|V 31 55 实现一个函数flatten(),该函数用来将链表扁平化成单个链表，扁平化的链表也应该被排序。例如，对于上述输入链表，输出链表应该为3->6->8->11->15->21->22->30->31->39->40->50->55		Python程序员面试算法宝典 https://blog.csdn.net/qingyuanluofeng/article/details/90114758
52	移动小球我有小球，从左到右一次编号为1,2,3,...,n 你可以执行两种指令: A X Y表示把小球X移动到小球Y的左边，B X Y表示把小球X移动到小球Y的右边。指令保证合法，即X不等于Y。输入小球个数n,指令条数m和m条指令，从左到右输出最后的序列。注意，n可能高达500000,而m可能高达100000 输入: 6 2 A 1 4 B 3 5 输出: 2 1 4 5 3 6		算法竞赛入门经典 https://blog.csdn.net/qingyuanluofeng/article/details/47730725