• 【数据结构】单链表经典面试题10道及详细思路代码

    目录

    1. 删除链表中等于给定值 val 的所有节点。

    2. 反转一个单链表。

    3. 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

    4. 输入一个链表，输出该链表中倒数第k个结点。

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

    6. 编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前 。

    7. 链表的回文结构。

    8. 输入两个链表，找出它们的第一个公共结点。

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

    10. 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 NULL

    1. 删除链表中等于给定值 val 的所有节点。

    leetcode 203 移除链表元素

     

    1. typedef struct ListNode Node;
    2. struct ListNode* removeElements(struct ListNode* head, int val){
    3.     Node* cur = head;
    4.     Node *prev = NULL;//保存cur的前一个结点
    5.     while(cur)
    6.     {
    7.  
    8.         if(cur->val == val)
    9.         {
    10.             if(NULL == prev)
    11.             {
    12.                 //需要删除的cur刚好是链表第一个结点，此时prev是空
    13.                 //需要修改head的指向
    14.                 head = cur->next;
    15.                 free(cur);
    16.                 cur = head;
    17.             }
    18.             else
    19.             {
    20.                  //删除cur
    21.                  //让prev的next指向此时cur的next
    22.                    prev->next = cur->next;
    23.                   free(cur);
    24.                  //将prev赋值给cur
    25.                   cur = prev->next;
    26.             }
    27.            
    28.         }
    29.         else
    30.         {
    31.             prev = cur;
    32.             cur = cur->next;
    33.         }
    34.     }
    35.     return head;
    36. }

    2. 反转一个单链表。

    leetcode 206 反转链表

    1. typedef struct ListNode Node;
    2. struct ListNode* reverseList(struct ListNode* head){
    3.  
    4.     Node* prev = NULL;
    5.     Node* cur = head;
    6.     Node* next = NULL;
    7.         //以左图为例子，此时，cur在1，其他在null
    8.  
    9.     while(cur)
    10.     {
    11.         next = cur->next; //next在2，cur在1，prev在空
    12.         cur->next = prev;//改变链表指向，让cur指向空
    13.         prev = cur; //prev在1
    14.         cur = next;//cur在2，依次改变链表每个结点指向
    15.     }
    16.     return prev;
    17.  
    18. }

     

    3. 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

    leetcode 876

    给定一个头结点为 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

    思路:

    给两个指针fast slow，fast每次走2步，slow走一步,fast到末尾，slow在中间

    1. typedef struct ListNode Node;
    2. struct ListNode* middleNode(struct ListNode* head){
    3.     Node* fast = head;
    4.     Node* slow = head;
    5.  
    6.     //fast和接下来2步都不为空
    7.     //fast不为null，可以保证fast第一步成功
    8.     //fast->next 不为空，保证第二部走成功
    9.     while(fast &&  fast->next)
    10.     {
    11.         fast = fast->next->next;
    12.         slow = slow->next;
    13.     }
    14.  
    15.     return slow;
    16. }

     拓展：要求假设返回中间的第一个结点

    1. Node* fast = head;
    2.     Node* slow = head;
    3.     Node* prev =NULL;
    4.  
    5.     while(fast &&  fast->next)
    6.     {
    7.         fast = fast->next->next;
    8.         prev = slow;
    9.         slow = slow->next;
    10.     }
    11.     if(fast)  //总数是奇数
    12.     {
    13.         return slow;
    14.     }
    15.     else  //总数是偶数
    16.     {
    17.         return prev;
    18.     }

    4. 输入一个链表，输出该链表中倒数第k个结点。

    最优思路：先让front走k步，再让back和front同时走，当front到末尾,back就是倒数第k结点

    OJ链接

    1. struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    2.     // write code here
    3.     //先让front走k步，再让back和front同时走，当front到末尾,back就是倒数第k结点
    4.     //1.对参数进行检测
    5.     if(NULL ==pListHead || k <= 0)
    6.         return NULL;
    7.     
    8.     //2.定义两个指针
    9.     struct ListNode* front = pListHead;
    10.     struct ListNode* back = pListHead;
    11.     
    12.     //注意K可能会大于链表长度
    13.     while(k)
    14.     {
    15.         if(NULL == front)
    16.             return NULL;
    17.         
    18.        front = front->next;
    19.         k--;
    20.     }
    21.     while(front != NULL)
    22.     {
    23.         front = front->next;
    24.         back = back->next;
    25.     }
    26.     return back;    
    27. }

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

    （Leetcode 21.合并两个有序链表）

     思路：

    1.先创建一个新的链表

    2.让cur1 和 cur2遍历两个链表，遇到的节点逐个比较，将值小的节点往新链表的末尾tail进行尾插

    3.上述循环结束后，要判断有无链表还有剩余元素，把剩余的元素尾插到新链表的末尾。

    1. typedef struct ListNode Node;
    2. struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    3.     if(NULL == list1)
    4.           return list2;
    5.  
    6.     if(NULL == list2)
    7.           return list1;
    8.     //走到这里，说明两个链表均不为空,需要合并
    9.     Node* pNewList =NULL;
    10.     Node* cur1 = list1;
    11.     Node* cur2 = list2;
    12.     //在pnewlist中插入第一个节点，第一个节点要修改pnewlist的指向
    13.     if(cur1 -> val <= cur2->val)
    14.     {
    15.         pNewList = cur1;
    16.         cur1 = cur1->next;
    17.     }
    18.     else
    19.     {
    20.         pNewList = cur2;
    21.         cur2 = cur2->next;
    22.     }
    23.     Node* tail = pNewList;//新链表的尾部
    24.  
    25.     //让cur1 和 cur2遍历两个链表，遇到的节点逐个比较
    26.     //将值小的节点往新链表的末尾tail进行尾插
    27.  
    28.     while(cur1  && cur2)
    29.     {
    30.         if(cur1->val <= cur2->val)
    31.         {
    32.             tail->next = cur1;
    33.             cur1 = cur1->next;  
    34.         }
    35.         else
    36.         {
    37.             tail->next = cur2;
    38.             cur2 = cur2->next;
    39.         }
    40.          tail = tail->next;
    41.     }
    42.     if(cur1)
    43.     {
    44.         tail->next =cur1;
    45.     }
    46.     else if(cur2)
    47.     {
    48.         tail->next = cur2;
    49.     }
    50.     else{
    51.         return pNewList;
    52.     }
    53.     return pNewList;
    54. }

    6. 编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前 。

    OJ链接

    思路：

    1.创建两个链表，一个链表尾插值小于x的节点，另一个链表中插值大于等于x的节点

    2.遍历原链表，将链表中的节点往两个新链表中尾插--新链表最好将其给成带头节点的单链表

    3.将两个链表拼接

    1. class Partition {
    2. public:
    3.     ListNode* partition(ListNode* pHead, int x) {
    4.         if(NULL == pHead)
    5.             return pHead;
    6.         
    7.         //less链表中尾插小于x的节点
    8.         ListNode less(0);
    9.         ListNode* lessTail = &less;
    10.         
    11.         //尾插大于等于x的节点
    12.         ListNode greater(0);
    13.         ListNode* greaterTail = &greater;
    14.         
    15.         ListNode* cur = pHead;
    16.         
    17.         //利用cur去遍历phead
    18.         while(cur)
    19.         {
    20.             if(cur->val < x)
    21.             {
    22.                 lessTail->next = cur;
    23.                 lessTail = lessTail->next;   
    24.             }
    25.             else
    26.             {
    27.                 greaterTail->next = cur;
    28.                 greaterTail = greaterTail->next;
    29.             }
    30.               cur = cur->next;
    31.         }
    32.         
    33.         //拼接两个链表
    34.         lessTail ->next = greater.next;
    35.         greaterTail->next = NULL;
    36.         
    37.         return less.next; 
    38.     }
    39. };

    7. 链表的回文结构。

    对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。OJ链接

    思路1：

    题目中条件：保证链表长度小于等于900，所以额外空间创建如下 为o(1)

    1.给一个900的Int类型的数组

    2.遍历链表，让每个节点的值放入数组

    3.检测数组中保存的元素是否为回文结构

    1. class PalindromeList {
    2. public:
    3.     bool chkPalindrome(ListNode* A) {
    4.         int array[900];
    5.         
    6.         ListNode* cur = A;
    7.         int size = 0;
    8.         //遍历链表
    9.         while(cur)
    10.         {
    11.             array[size] = cur-> val;
    12.             cur = cur->next;
    13.             size++;
    14.         }
    15.         
    16.         int left = 0;
    17.         int right = size-1;
    18.         while(left < right)
    19.         {
    20.             if(array[left] != array[right])
    21.             {
    22.                 return false;
    23.             }
    24.             else
    25.             {
    26.                 left++;
    27.                 right--;
    28.             }
    29.         }
    30.         return true ;
    31.     }
    32. };

    对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。（去掉一个条件）

    思路2：
    1.找到链表的中间节点，从中间节点的位置将链表分开，形成2个链表---->找中间节点:采用快慢指针ok
    2.对后半部分进行逆置---链表的逆置ok
    3.将两个链表从前往后逐个节点进行比对，如果比对之后发现所有节点的值域都相同，则是回文链表，否则不是
    4.将链表还原成原链表
    注意:一般情况下不要破坏链表的结构，如果破坏了最后最好将其恢复

    1. class PalindromeList {
    2. public:
    3.     ListNode* getMiddleNode(ListNode* plist)
    4.     {
    5.         ListNode* fast = plist;
    6.         ListNode* slow = plist;
    7.         
    8.         while(fast && fast->next)
    9.         {
    10.             fast = fast->next->next;
    11.             slow = slow->next;
    12.         }
    13.         return slow;
    14.     }   
    15.         ListNode* reverseList(ListNode* plist)
    16.         {
    17.             ListNode* cur = plist;
    18.             ListNode* prev = NULL;
    19.             ListNode* next = NULL;
    20.             
    21.             while(cur)
    22.             {
    23.                 next = cur->next;
    24.                 cur->next = prev;
    25.                 prev = cur;
    26.                 cur = next;
    27.             }
    28.             return prev;
    29.         }
    30.         
    31.         bool chkPalindrome(ListNode* A)
    32.         {
    33.             if(NULL == A || NULL == A->next)
    34.                 return true;
    35.             //找到A链表中间节点，然后从中间节点的位置将其断开
    36.             ListNode* list1 = A;
    37.             ListNode* midNode = getMiddleNode(A);
    38.             ListNode* list2 = midNode->next;
    39.             midNode->next = NULL;
    40.             
    41.             //将后半部分进行逆置
    42.             list2 = reverseList(list2);
    43.             
    44.             //将list1和list2中的节点逐个比较
    45.             bool ret = true;
    46.             ListNode* cur1 = list1;
    47.             ListNode* cur2 = list2;
    48.             
    49.             while(cur1 && cur2)
    50.             {
    51.                 if(cur1->val != cur2->val)
    52.                 {
    53.                     ret = false;
    54.                     break;
    55.                 }
    56.                 
    57.                 cur1 = cur1->next;
    58.                 cur2 = cur2->next;
    59.             }
    60.             //还原链表
    61.             list2 = reverseList(list2);
    62.             midNode->next = list2;
    63.             
    64.             return ret;
    65.         }  
    66. };

    8. 输入两个链表，找出它们的第一个公共结点。

    leetcode 160.相交链表

    下面是两个节点相交的各类情况：

     

     在相交的情况下，求交点的方式：

    1.让较长的链表先走两个链表的差值步数

    2.在让两个链表同时往后走，直到遇到地址相同的交点

    1. struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    2.     //参数检测，如果有一个链表为空，不可能相交
    3.     if(NULL == headA || NULL == headB)
    4.     {
    5.         return NULL;
    6.     }
    7.     
    8.     //1.检测headA和headB是否相交
    9.     //分别找到两个链表最后一个节点，相同就相交，不同则不交
    10.     struct ListNode* curA = headA;
    11.     int sizeA = 1;
    12.     int sizeB = 1;
    13.     while(curA ->next)
    14.     {
    15.         curA = curA->next;
    16.         sizeA++;
    17.     }
    18.     struct ListNode* curB = headB;
    19.     while(curB->next)
    20.     {
    21.         curB = curB->next;
    22.         sizeB++;
    23.     }
    24.     if(curB != curA)
    25.           return NULL;
    26.  
    27.     //2.执行到此处说明相交
    28.     int gap = sizeA - sizeB;
    29.     curA = headA;
    30.     curB = headB;
    31.     if(gap > 0)
    32.     {
    33.         //headA长
    34.         while (gap--)
    35.         {
    36.             curA =  curA->next;
    37.         }
    38.     }
    39.     else
    40.     {
    41.         while(gap++)
    42.         {
    43.             curB = curB->next;
    44.         }
    45.     }
    46.     while(curA != curB)
    47.     {
    48.         curA = curA->next;
    49.         curB =  curB->next;
    50.     }
    51.     return curA;   
    52. }

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

    leetcode 141，环形链表

    给你一个链表的头节点 head ，判断链表中是否有环。

    如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。

    思路：

    快慢指针，即慢指针一次走一步，快指针一次走两步，两个指针从链表其实位置开始运行，如果链表带环则一定会在环中相遇，否则快指针率先走到链表的末尾
    为什么快指针每次走两步，慢指针走一步可以？
    假设链表带环，两个指针最后都会进入环，快指针先进环，慢指针后进环。当慢指针刚进环时，可
    能就和快指针相遇了，最差情况下两个指针之间的距离刚好就是环的长度。此时，两个指针每移动
    一次，之间的距离就缩小一步，不会出现每次刚好是套圈的情况，因此：在满指针走到一圈之前，
    快指针肯定是可以追上慢指针的，即相遇
    快指针如果走3、4步，可能存在永远不能遇到的可能

     

    1. bool hasCycle(struct ListNode *head) {
    2.     struct ListNode* fast = head;
    3.     struct ListNode* slow = head;
    4.  
    5.     while(fast && fast->next)
    6.     {
    7.         fast= fast->next->next;
    8.         slow = slow->next;
    9.  
    10.         if(fast == slow)
    11.             return true;
    12.     }
    13.     return false;
    14.     
    15. }

    10. 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 NULL

    leetcode 142环形链表2

    如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。

     

     ​​​​​​​

     

     

    1. struct ListNode *detectCycle(struct ListNode *head) {
    2.  
    3.     struct ListNode* fast = head;
    4.     struct ListNode* slow = head;
    5.     int hasCycle = 0; //标记链表是否带环
    6.  
    7.     while(fast && fast->next)
    8.     {
    9.         fast= fast->next->next;
    10.         slow = slow->next;
    11.  
    12.         if(fast == slow)
    13.         {
    14.             hasCycle = 1;
    15.             break;
    16.         }
    17.     }
    18.  
    19.     
    20.     if(!hasCycle)//链表不带环
    21.         return NULL;
    22.  
    23.     struct ListNode* pH = head;
    24.     struct ListNode* pM = fast;  //相遇点
    25.     while(pH != pM)
    26.     {
    27.         pH = pH->next;
    28.         pM = pM->next;
    29.     }
    30.     return pM;    
    31. }

  • 相关阅读:
    【JavaEE】Spring AOP （面向切面）详解
    祝贺！Databend Cloud 入驻 AWS 云市场
    一个简单的微信小程序表单提交样式模板
    Kubernetes教程(十一)---使用 KubeClipper 通过一条命令快速创建 k8s 集群
    C语言——深度剖析数据在内存中的存储
    外包干了5天，技术明显退步
    无人不识又无人不迷糊的this
    数据分析和可视化必备的几大软件，你用过几个？
    AI 视频 | 文本生视频工具又迎来重大更新，Runway Gen-2 到底有多强？Gen-2 怎么用（保姆级教程）
    数据脱敏的功能与技术原理【详解】
  • 原文地址：https://blog.csdn.net/weixin_59215611/article/details/126518620