【Leetcode解题报告】单链表结点删除相关问题
时间： 23:37:06
&&&& 阅读：51
&&&& 评论：
&&&& 收藏：0
标签：Leetcode 203 Remove Linked List Elements
　　Remove all elements from a linked list of integers that have value val. For example, given 1 -& 2 -& 6 -& 3 -& 4 -& 5 -& 6, val = 6. Return 1 -& 2 -& 3 -& 4 -& 5.&
分析与解法
　　遍历链表，用一个指针指向遍历到当前结点的前驱结点，方便删除；如果当前结点的值为val，则删除。参考代码如下所示：
* Definition for singly-linked list.
* struct ListNode
ListNode *
ListNode(int x) : val(x), next(NULL) {}
10 class Solution
12 public:
ListNode* removeElements(ListNode* head, int val)
ListNode new_head_node(0); new_head_node.next =
ListNode *pre = &new_head_node, *p =
if (p-&val == val)
ListNode *q =
pre-&next =
// 释放结点
return new_head_node.
Leetcode 83 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.&
分析与解法
　　遍历链表，查看当前结点的值是否与其前驱结点相同，如果相同，则删除；否则不删除。参考代码如下：
1 class Solution
ListNode* deleteDuplicates(ListNode* head)
if (!head || !head-&next) return
ListNode *pre = head, *p = head-&
if (p-&val == pre-&val)
ListNode *q =
pre-&next =
Leetcode 82 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.&
分析与解法
(1) 非递归解法
　　遍历链表，看当前结点值是否与后继结点值相等(如果后继不为空)，如果不相等，则继续遍历；否则，删除与当前结点值相同的所有结点，包括当前结点，使用一个指针指向遍历到当前结点的前驱结点，方便进行删除操作。参考代码如下：
1 class Solution
ListNode* deleteDuplicates(ListNode* head)
ListNode new_head_node(0); new_head_node.next =
ListNode *pre = &new_head_node, *p =
while (p && p-&next)
if (p-&val != p-&next-&val)
pre-&next =
while (p && p-&next && p-&val == p-&next-&val)
ListNode *q =
ListNode *q =
pre-&next = p-&
else pre-&next = NULL;
return new_head_node.
(2) 递归解法
　　一个看起来更容易理解的方法，参考代码如下：
1 class Solution
ListNode* deleteDuplicates(ListNode* head)
if (!head || !head-&next) return
ListNode *p =
if (p-&val != p-&next-&val)
p-&next = deleteDuplicates(p-&next);
while (p-&next && p-&val == p-&next-&val)
ListNode *q =
ListNode *q = p-&
return deleteDuplicates(q);
Leetcode 19 Remove Nth Node fron 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个结点的前驱结点，然后删除，参考代码如下所示：
1 class Solution
ListNode* removeNthFromEnd(ListNode* head, int n)
ListNode *nhead = new ListNode(0); nhead-&next =
ListNode *p = head, *q = nhead, *s = NULL;
for (int i = 0; i & i++) p = p-&
q-&next = s-&
return nhead-&
Leetcode 237 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.&
分析与解法　　
　　在删除结点时，如果我们知道要删除结点的前驱结点，那么，删除这个结点将比较容易，换句话说，删除一个结点的后继结点是比较容易实现的；而本题并不知道前驱，也没有办法获得前驱结点的位置。可以换一个思路，将当前结点的后继删除，这是比较容易做到的，不过，在删除其后继结点之前，需要将后继结点的值赋给当前结点，这样虽然删除的是其后继，但实际保留了后继的值，删除了当前结点的值。参考代码如下所示：
1 class Solution {
void deleteNode(ListNode* node)
node-&val = node-&next-&
ListNode *s = node-&
node-&next = s-&
&&国之画&&&& &&&&chrome插件
版权所有 京ICP备号-2
迷上了代码！常见链表问题整理
链表问题在面试过程中也是很重要也很基础的一部分，链表本身很灵活，很考查功底，所以是很值得考的地方。我将复习过程中觉得比较好的链表问题整理了下。
下面是本文所要用到链表节点的定义：
struct Node{
1. 在O(1)时间删除链表节点
题目描述：给定链表的头指针和一个节点指针，在O(1)时间删除该节点。[Google面试题]
分析：本题与《编程之美》上的「从无头单链表中删除节点」类似。主要思想都是「狸猫换太子」，即用下一个节点数据覆盖要删除的节点，然后删除下一个节点。但是如果节点是尾节点时，该方法就行不通了。
代码如下：
//O(1)时间删除链表节点，从无头单链表中删除节点
void deleteRandomNode(Node *cur)
assert(cur != NULL);
assert(cur-&next != NULL);
//不能是尾节点
Node* pNext = cur-&
cur-&data = pNext-&
cur-&next = pNext-&
2. 单链表的转置
题目描述：输入一个单向链表，输出逆序反转后的链表
分析：链表的转置是一个很常见、很基础的数据结构题了，非递归的算法很简单，用三个临时指针 pre、head、next 在链表上循环一遍即可。递归算法也是比较简单的，但是如果思路不清晰估计一时半会儿也写不出来吧。
下面是循环版本和递归版本的链表转置代码：
//单链表的转置,循环方法
Node* reverseByLoop(Node *head)
if(head == NULL || head-&next == NULL)
Node *pre = NULL;
Node *next = NULL;
while(head != NULL)
next = head-&
head-&next =
//单链表的转置,递归方法
Node* reverseByRecursion(Node *head)
//第一个条件是判断异常，第二个条件是结束判断
if(head == NULL || head-&next == NULL)
Node *newHead = reverseByRecursion(head-&next);
head-&next-&next =
head-&next = NULL;
return newH
//返回新链表的头指针
3. 求链表倒数第k个节点
题目描述：输入一个单向链表，输出该链表中倒数第k个节点，链表的倒数第0个节点为链表的尾指针。
分析：设置两个指针 p1、p2，首先 p1 和 p2 都指向 head，然后 p2 向前走 k 步，这样 p1 和 p2 之间就间隔 k 个节点，最后 p1 和 p2 同时向前移动，直至 p2 走到链表末尾。
代码如下：
//倒数第k个节点
Node* theKthNode(Node *head,int k)
if(k & 0) return NULL;
//异常判断
Node *slow,*
slow = fast =
for(;i&0 && fast!=NULL;i--)
fast = fast-&
return NULL;
//考虑k大于链表长度的case
while(fast != NULL)
slow = slow-&
fast = fast-&
4. 求链表的中间节点
题目描述：求链表的中间节点，如果链表的长度为偶数，返回中间两个节点的任意一个，若为奇数，则返回中间节点。
分析：此题的解决思路和第3题「求链表的倒数第 k 个节点」很相似。可以先求链表的长度，然后计算出中间节点所在链表顺序的位置。但是如果要求只能扫描一遍链表，如何解决呢？最高效的解法和第3题一样，通过两个指针来完成。用两个指针从链表头节点开始，一个指针每次向后移动两步，一个每次移动一步，直到快指针移到到尾节点，那么慢指针即是所求。
代码如下：
//求链表的中间节点
Node* theMiddleNode(Node *head)
if(head == NULL)
return NULL;
Node *slow,*
slow = fast =
//如果要求在链表长度为偶数的情况下，返回中间两个节点的第一个，可以用下面的循环条件
//while(fast && fast-&next != NULL && fast-&next-&next != NULL)
while(fast != NULL && fast-&next != NULL)
fast = fast-&next-&
slow = slow-&
5. 判断单链表是否存在环
题目描述：输入一个单向链表，判断链表是否有环？
分析：通过两个指针，分别从链表的头节点出发，一个每次向后移动一步，另一个移动两步，两个指针移动速度不一样，如果存在环，那么两个指针一定会在环里相遇。
代码如下：
//判断单链表是否存在环,参数circleNode是环内节点，后面的题目会用到
bool hasCircle(Node *head,Node *&circleNode)
Node *slow,*
slow = fast =
while(fast != NULL && fast-&next != NULL)
fast = fast-&next-&
slow = slow-&
if(fast == slow)
circleNode =
6. 找到环的入口点
题目描述：输入一个单向链表，判断链表是否有环。如果链表存在环，如何找到环的入口点？
解题思路：由上题可知，按照 p2 每次两步，p1 每次一步的方式走，发现 p2 和 p1 重合，确定了单向链表有环路了。接下来，让p2回到链表的头部，重新走，每次步长不是走2了，而是走1，那么当 p1 和 p2 再次相遇的时候，就是环路的入口了。
为什么？：假定起点到环入口点的距离为 a，p1 和 p2 的相交点M与环入口点的距离为b，环路的周长为L，当 p1 和 p2 第一次相遇的时候，假定 p1 走了 n 步。那么有：
p1走的路径：a+b ＝ n；
p2走的路径：a+b+k*L = 2*n； p2 比 p1 多走了k圈环路，总路程是p1的2倍
根据上述公式可以得到k*L=a+b=n显然，如果从相遇点M开始，p1 再走 n 步的话，还可以再回到相遇点，同时p2从头开始走的话，经过n步，也会达到相遇点M。
显然在这个步骤当中 p1 和 p2 只有前 a 步走的路径不同，所以当 p1 和 p2 再次重合的时候，必然是在链表的环路入口点上。
代码如下：
//找到环的入口点
Node* findLoopPort(Node *head)
//如果head为空，或者为单结点，则不存在环
if(head == NULL || head-&next == NULL) return NULL;
Node *slow,*
slow = fast =
//先判断是否存在环
while(fast != NULL && fast-&next != NULL)
fast = fast-&next-&
slow = slow-&
if(fast == slow)
if(fast != slow) return NULL;
//不存在环
//快指针从头开始走，步长变为1
while(fast != slow)
//两者相遇即为入口点
fast = fast-&
slow = slow-&
7. 编程判断两个链表是否相交
题目描述：给出两个单向链表的头指针（如下图所示），
比如h1、h2，判断这两个链表是否相交。这里为了简化问题，我们假设两个链表均不带环。
解题思路：
直接循环判断第一个链表的每个节点是否在第二个链表中。但，这种方法的时间复杂度为O(Length(h1) * Length(h2))。显然，我们得找到一种更为有效的方法，至少不能是O（N^2）的复杂度。
针对第一个链表直接构造hash表，然后查询hash表，判断第二个链表的每个节点是否在hash表出现，如果所有的第二个链表的节点都能在hash表中找到，即说明第二个链表与第一个链表有相同的节点。时间复杂度为为线性：O(Length(h1) + Length(h2))，同时为了存储第一个链表的所有节点，空间复杂度为O(Length(h1))。是否还有更好的方法呢，既能够以线性时间复杂度解决问题，又能减少存储空间？
转换为环的问题。把第二个链表接在第一个链表后面，如果得到的链表有环，则说明两个链表相交。如何判断有环的问题上面已经讨论过了，但这里有更简单的方法。因为如果有环，则第二个链表的表头一定也在环上，即第二个链表会构成一个循环链表，我们只需要遍历第二个链表，看是否会回到起始点就可以判断出来。这个方法的时间复杂度是线性的，空间是常熟。
进一步考虑&如果两个没有环的链表相交于某一节点，那么在这个节点之后的所有节点都是两个链表共有的&这个特点，我们可以知道，如果它们相交，则最后一个节点一定是共有的。而我们很容易能得到链表的最后一个节点，所以这成了我们简化解法的一个主要突破口。那么，我们只要判断两个链表的尾指针是否相等。相等，则链表相交；否则，链表不相交。
所以，先遍历第一个链表，记住最后一个节点。然后遍历第二个链表，到最后一个节点时和第一个链表的最后一个节点做比较，如果相同，则相交，否则，不相交。这样我们就得到了一个时间复杂度，它为O((Length(h1) + Length(h2))，而且只用了一个额外的指针来存储最后一个节点。这个方法时间复杂度为线性O(N)，空间复杂度为O(1)，显然比解法三更胜一筹。
解法四的代码如下：
//判断两个链表是否相交
bool isIntersect(Node *h1,Node *h2)
if(h1 == NULL || h2 == NULL)
//异常判断
while(h1-&next != NULL)
while(h2-&next != NULL)
if(h1 == h2)
//尾节点是否相同
8. 扩展：链表有环，如何判断相交
题目描述：上面的问题都是针对链表无环的，那么如果现在，链表是有环的呢?上面的方法还同样有效么?
分析：如果有环且两个链表相交，则两个链表都有共同一个环，即环上的任意一个节点都存在于两个链表上。因此，就可以判断一链表上俩指针相遇的那个节点，在不在另一条链表上。
代码如下：
//判断两个带环链表是否相交
bool isIntersectWithLoop(Node *h1,Node *h2)
Node *circleNode1,*circleNode2;
if(!hasCircle(h1,circleNode1))
//判断链表带不带环，并保存环内节点
//不带环，异常退出
if(!hasCircle(h2,circleNode2))
Node *temp = circleNode2-&
while(temp != circleNode2)
if(temp == circleNode1)
temp = temp-&
9. 扩展：两链表相交的第一个公共节点
题目描述：如果两个无环单链表相交，怎么求出他们相交的第一个节点呢？
分析：采用对齐的思想。计算两个链表的长度 L1 , L2，分别用两个指针 p1 , p2 指向两个链表的头，然后将较长链表的 p1（假设为 p1）向后移动L2 - L1个节点，然后再同时向后移动p1 , p2，直到p1 = p2。相遇的点就是相交的第一个节点。
代码如下：
//求两链表相交的第一个公共节点
Node* findIntersectNode(Node *h1,Node *h2)
int len1 = listLength(h1);
//求链表长度
int len2 = listLength(h2);
//对齐两个链表
if(len1 & len2)
for(int i=0;i
for(int i=0;i
while(h1 != NULL)
if(h1 == h2)
return h1;
return NULL;
可以发现，在链表的问题中，通过两个的指针来提高效率是很值得考虑的一个解决方案，所以一定要记住这种解题思路。记住几种典型的链表问题解决方案，很多类似的题目都可以转换到熟悉的问题再解决。