链表算法经典十题总结

2023-07-29 08:25| 来源: 网络整理| 查看: 265

前言

由于前面写了一些数据结构的相关的文章，但是都是偏基本的数据结构知识，并没有实际的算法题加以实践，故整理十道题目，都是比较常见的链表类的算法题，也参考了优秀的博客。预备的数据结构知识点：

数据结构绪论循序渐进学习栈和队列循序渐进学习数据结构之线性表循序渐进学习时间复杂度

1.链表的倒数第K个结点问题描述：

输入一个链表，输出该链表中倒数第k个结点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾结点是倒数第1个结点。例如一个链表有6个结点，从头结点开始它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个结点是值为4的结点,需要保证时间复杂度。

算法思路：

设置两个指针p1,p2，从头到尾开始出发，一个指针先出发k个节点，然后第二个指针再进行出发，当第一个指针到达链表的节点的时候，则第二个指针表示的位置就是链表的倒数第k个节点的位置。

代码如下： //倒数第k个结点 ListNode findKth(ListNode head,int k){ ListNode cur=head; ListNode now=head; int i=0; while(cur!=null&i++next; } while(cur!=null){ now=now->next; cur=cur->next; } }

总结：当我们用一个指针遍历链表不能解决问题的时候，可以尝试用两个指针来遍历链表。可以让其中一个指针遍历的速度快一些（比如一次在链表上走两步），或者让它先在链表上走若干步。

2.从尾到头打印链表（递归和非递归）问题描述：

输入一个单链表链表，从尾到头打印链表每个节点的值。输入描述：输入为链表的表头；输出描述：输出为需要打印的“新链表”的表头。

算法思路：

首先我们想到从尾到头打印出来，由于单链表的查询只能从头到尾，所以可以想出栈的特性，先进后出。所以非递归可以把链表的点全部放入一个栈当中，然后依次取出栈顶的位置即可。

代码如下： //非递归 void PrintReversing(ListNode * head){ //利用一个栈 Stack stack; ListNode *node=head->next; //将链表的结点压入 while(node!=null){ stack.push(node); node=node->next; } ListNode *popNode; while(stack.isEmpty()){ //获得最上面的元素 popNode=stack.top(); //打印 printf("%d\t",popNode->value); //弹出元素 stack.pop(); } /递归 void printRevese(ListNode *head){ if(head!=null){ if(head->next!=null){ printRevese(head->next); } print("%d\t",head->value); } }

非递归的描述当中，经常会用栈或者队列这些数据结构来改写一些递归的算法。其实递归的算法的时间复杂度是递归树的高度，所以递归的层数越高，时间复杂度也就会越高的。

3.如何判断一个链表有环问题描述：

有一个单向链表，链表当中有可能出现“环”，如何用程序判断出这个链表是有环链表？不允许修改链表结构。时间复杂度O(n)，空间复杂度O(1)。

算法思路：方法一、穷举遍历

首先从头节点开始，依次遍历单链表的每一个节点。每遍历到一个新节点，就从头节点重新遍历新节点之前的所有节点，用新节点ID和此节点之前所有节点ID依次作比较。如果发现新节点之前的所有节点当中存在相同节点ID，则说明该节点被遍历过两次，链表有环；如果之前的所有节点当中不存在相同的节点，就继续遍历下一个新节点，继续重复刚才的操作。

假设从链表头节点到入环点的距离是D，链表的环长是S。那么算法的时间复杂度是0+1+2+3+….+(D+S-1) = (D+S-1)(D+S)/2 ，可以简单地理解成 O(NN)。而此算法没有创建额外存储空间，空间复杂度可以简单地理解成为O(1)。

这种方法是暴力破解的方式，时间复杂度太高。

方法二、快慢指针

首先创建两个指针1和2，同时指向这个链表的头节点。然后开始一个大循环，在循环体中，让指针1每次向下移动一个节点，让指针2每次向下移动两个节点，然后比较两个指针指向的节点是否相同。如果相同，则判断出链表有环，如果不同，则继续下一次循环。

说明：在循环的环里面，跑的快的指针一定会反复遇到跑的慢的指针，比如：在一个环形跑道上，两个运动员在同一地点起跑，一个运动员速度快，一个运动员速度慢。当两人跑了一段时间，速度快的运动员必然会从速度慢的运动员身后再次追上并超过，原因很简单，因为跑道是环形的。

代码如下：

/** * 判断单链表是否存在环 * @param head * @return */ public static boolean isLoopList(ListNode head){ ListNode slowPointer, fastPointer; //使用快慢指针，慢指针每次向前一步，快指针每次两步 slowPointer = fastPointer = head; while(fastPointer != null && fastPointer.next != null){ slowPointer = slowPointer.next; fastPointer = fastPointer.next.next; //两指针相遇则有环 if(slowPointer == fastPointer){ return true; } } return false; } 4.链表中环的大小问题描述

有一个单向链表，链表当中有可能出现“环”，那么如何知道链表中环的长度呢？

算法思路

由[3.如何判断一个链表有环](# 3.如何判断一个链表有环)可以知道，快慢指针可以找到链表是否有环存在，如果两个指针第一次相遇后，第二次相遇是什么时候呢？第二次相遇是不是可以认为快的指针比慢的指针多跑了一个环的长度。所以找到第二次相遇的时候就找到了环的大小。

代码如下 //求环中相遇结点 public Node cycleNode(Node head){ //链表为空则返回null if(head == null) return null; Node first = head; Node second = head; while(first != null && first.next != null){ first = first.next.next; second = second.next; //两指针相遇，则返回相遇的结点 if(first == second) return first; } //链表无环，则返回null return null; } public int getCycleLength(Node head){ Node node = cycleNode(head); //node为空则代表链表无环 if(node == null) return 0; int length=1; Node current = node.next; //再次相遇则循环结束 while(current != node){ length++; current = current.next; } return length; } 5.链表中环的入口结点问题描述

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

算法思路

如果链表存在环，那么计算出环的长度n，然后准备两个指针pSlow，pFast，pFast先走n步，然后pSlow和pFase一块走，当两者相遇时，即为环的入口处；所以解决三个问题：如何判断一个链表有环；如何判断链表中环的大小；链表中环的入口结点。实际上最后的判断就如同链表的倒数第k个节点。

代码如下 public class Solution { public ListNode EntryNodeOfLoop(ListNode pHead) { if(pHead.next == null || pHead.next.next == null) return null; ListNode slow = pHead.next; ListNode fast = pHead.next.next; while(fast != null){ if(fast == slow){ fast = pHead; while(fast != slow){ fast = fast.next; slow = slow.next; } return fast; } slow = slow.next; fast = fast.next.next; } return null; } }

以上5题的套路其实都非常类似，第5题可以说是前面几道题的一个汇总题目吧，链表类的题利用快慢指针，两个指针确实挺多的，如下面题目7

6.单链表在时间复杂度为O(1)删除链表结点问题描述

给定单链表的头指针和一个结点指针，定一个函数在时间复杂度为O(1)删除链表结点

算法思路

根据了解的条件，如果只有一个单链表的头指针，链表的删除操作其实正常的是O（n）的时间复杂度。因为首先想到的是从头开始顺序遍历单链表，然后找到节点，再进行删除。但是这样的方式达到的时间复杂度并不是O（1）；实际上纯粹的删除节点操作，链表的删除操作是O（1）。前提是需要找到删除指定节点的前一个结点就可以。

那么是不是必须找到删除指定节点的前一个结点呢？如果我们删除的节点是A，那么我们把A下一个节点B和A的data进行交换，然后我们删除节点B，是不是也可以达到同样的效果。

答案是肯定的。既然不能在O(1)得到删除节点的前一个元素，但我们可以轻松得到后一个元素，这样，我们何不把后一个元素赋值给待删除节点，这样也就相当于是删除了当前元素。可见，该方法可行，但如果待删除节点为最后一个节点，则不能按照以上思路，没有办法，只能按照常规方法遍历，时间复杂度为O(n)，是不是不符合题目要求呢？可能很多人在这就会怀疑自己的思考，从而放弃这种思路，最后可能放弃这道题，这就是这道面试题有意思的地方，虽看简单，但是考察了大家的分析判断能力，是否拥有强大的心理，充分自信。其实我们分析一下，仍然是满足题目要求的，如果删除节点为前面的n-1个节点，则时间复杂度为O(1)，只有删除节点为最后一个时，时间复杂度才为O(n)，所以平均的时间复杂度为：（O(1) * (n-1) + O(n)）/n = O(1);仍然为O(1).

代码如下 /* Delete a node in a list with O(1) * input: pListHead - the head of list * pToBeDeleted - the node to be deleted */ struct ListNode { int m_nKey; ListNode* m_pNext; }; void DeleteNode(ListNode *pListHead, ListNode *pToBeDeleted) { if (!pListHead || !pToBeDeleted) return; if (pToBeDeleted->m_pNext != NULL) { ListNode *pNext = pToBeDeleted->m_pNext; pToBeDeleted->m_pNext = pNext->m_pNext; pToBeDeleted->m_nKey = pNext->m_nKey; delete pNext; pNext = NULL; } else { //待删除节点为尾节点 ListNode *pTemp = pListHead; while(pTemp->m_pNext != pToBeDeleted) pTemp = pTemp->m_pNext; pTemp->m_pNext = NULL; delete pToBeDeleted; pToBeDeleted = NULL; } }

题目的考虑的点，也很特别

7.两个链表的第一个公共结点问题描述

输入两个单链表，找出他们的第一个公共结点。

算法思路

我们了解到单链表的指针是指向下一个节点的，如果两个单链表的第一个公共节点就说明他们后面的节点都是在一起的。类似下图，由于两个链表的长度可能是不一致的，所以首先比较两个链表的长度m，n，然后用两个指针分别指向两个链表的头节点，让较长的链表的指针先走|m-n|个长度，如果他们下面的节点是一样的，就说明出现了第一个公共节点。

代码如下 /* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/ public class Solution { public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) { if (pHead1 == null||pHead2 == null) { return null; } int count1 = 0; ListNode p1 = pHead1; while (p1!=null){ p1 = p1.next; count1++; } int count2 = 0; ListNode p2 = pHead2; while (p2!=null){ p2 = p2.next; count2++; } int flag = count1 - count2; if (flag > 0){ while (flag>0){ pHead1 = pHead1.next; flag --; } while (pHead1!=pHead2){ pHead1 = pHead1.next; pHead2 = pHead2.next; } return pHead1; } if (flag

【本文地址】

公司简介

联系我们