【数据结构基础经典面试Oj题】单向链表经典Oj题目第一弹（做题思路加逻辑分析加代码实操，一应俱全的汇总）

admin 管理员组

文章数量: 887016

【数据结构基础/经典面试Oj题】单向链表经典Oj题目第一弹（做题思路加逻辑分析加代码实操，一应俱全的汇总）

目录

单向链表经典Oj题目第一弹 (Singly-Linked List Oj)

条件

删除指定值的特定节点

反转一个单链表。

返回中间节点

链表中倒数第k个结点

归并(合并两个有序链表)

链表分割

链表的回文结构

输入两个链表，找出它们的第一个公共节点

---

单向链表经典Oj题目第一弹 (Singly-Linked List Oj)

条件

 //   struct ListNode// {//     int val;//     struct ListNode *next;// };//       typedef struct ListNode ListNode;

删除指定值的特定节点

思路

1. 定义cur指针去从头开始遍历整个链表。

2. 定义prev指针去指向cur的前一个地址。

3. 找到cur所指向的值等于指定值的时候，进行free和cur的再指向。

4. 注意区分考虑cur为第一个节点的情况(这时prev不能用)。

代码

  struct ListNode *removeElements(struct ListNode *head, int val){struct ListNode *prev = NULL, *cur = head;while (cur){if (cur->val == val){//头删if (cur == head){head = cur->next;free(cur);cur = head;}//中间删除else{prev->next = cur->next;free(cur);cur = prev->next;}}else{//迭代，往后走prev = cur;cur = cur->next;}}return head;}

反转一个单链表。

思路1

我们都知道链表是前一个里面存了后一个的地址，如果我们反转链表，实际上就是在后一个的节点里面去存前一个的地址。

所有的数据结构的解题都要涉及到画图，本题也要去画图解决。

首先我们需要判断如果反转，我们需要什么条件。

逻辑分析

第一，我们需要让后一个节点指向前一个节点，而且指向之后，后一个节点就找不到原本它的下一个节点了，所以我们需要设计三个指针变量。

     ListNode *n1, *n2, *n3;n1 = NULL;n2 = head;n3 = head->next;

核心逻辑是进行反转，也就是把前一个的地址给到下一个的节点里面去。

随后迭代条件是把整体的n1、n2、n3的指针向后推移，也就是把n2给到n1，n3给到n2，然后n3->next给到n3。做到这样就可以了。

    n1 = n2;n2 = n3;n3 = n3->next;

但是有一些问题，我们需要仔细考虑，如果n3为NULL，n3->next本身就是越界访问，会报错，所以我们需要单独设计条件判断。

 if (n3)n3 = n3->next;

此外，还需要考虑，如果传过来的节点本身为空的话，我们反转是没有意义的，直接传递空指针回去即可。

  if (head == NULL){return;}

代码

综合起来就是：

 struct ListNode *reverseList(struct ListNode *head){if (head == NULL){return;}ListNode *n1, *n2, *n3;n1 = NULL;n2 = head;n3 = head->next;​while (n2){//反转n2->next = n1;//迭代走n1 = n2;n2 = n3;if (n3)n3 = n3->next;}return n1;}

思路2

我们也可以去原链表中的节点，头插到newhead新链表中。

逻辑分析

构建一个新链表，只需要把依次把原链表中的节点头插到新链表中，但是头插之后会发现这个节点的指向被抹去了，也就是我们无法通过这个节点再找到原来链表中的下一个节点。所以我们需要定义next去记忆下一个节点的地址。

我们需要学习每个题目都要去画图处理，画图的目的是分析清楚我们的

• 初始条件(定义什么变量)

• 中间逻辑(核心逻辑，也就是通过什么手段完成题目的要求)

• 迭代逻辑(如何去走一个循环，即完成一步之后如何进行下一步)

• 结束条件(什么时候中止循环)

对这个题目，我们同样的，如果想要头插的做法，初始条件分析在上面已经进行了：

头插之后会发现这个节点的指向被抹去了，也就是我们无法通过这个节点再找到原来链表中的下一个节点。所以我们需要定义next去记忆下一个节点的地址。 即：

 ListNode *cur = head;ListNode *newhead = NULL;ListNode *next = cur->next;

随后我们进行中间逻辑的编写，即头插，对于头插我们都已经轻车熟路了：

         //头插cur->next = newhead;newhead = cur;

迭代条件：

 cur = next;

中止条件：

当cur为空的时候，我们不能在继续执行头插操作，即是循环中止。

 while(cur)

代码

 struct ListNode *reverseList(struct ListNode *head){ListNode *cur = head;ListNode *newhead = NULL;while(cur){ListNode *next = cur->next;//头插cur->next = newhead;newhead = cur;//迭代cur = next;}return newhead;}

返回中间节点

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

思路1

遍历一次，算出长度，分析奇偶情况并找到中间值

思路2

使用“快慢指针”，定义slow和fast，slow每次走一步，fast每次走两步。

通过画图可以知道，中止条件应该是fast或者fast->next为空，这时候的slow就是需要返回的值。

代码

 struct ListNode* middleNode(struct ListNode* head){struct ListNode *slow = head, *fast = head;while(fast&&fast->next){fast = fast->next->next;slow = slow->next;}return slow;}

链表中倒数第k个结点

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

思路1

遍历链表求得节点个数，然后遍历第二遍找到倒数第k个。

思路2

快慢指针，slow和fast定义好之后，fast先走k步，slow和fast再一起走，fast == NULL时，slow就是倒数第k个。

 struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {struct ListNode* fast = pListHead, *slow = pListHead;while (k--) { //k--是走k步，--k是走k-1步，搞不清楚就带值//k大于链表长度if (!fast) {return NULL;}fast = fast->next;}while (fast) {fast = fast->next;slow = slow->next;}return slow;}

归并(合并两个有序链表)

思路

一次比较链表中的节点，每次取小的节点尾插到新链表即可。

逻辑分析

如果尾插到新链表的话，我们需要给定两个指针去指向list1和list2链表，并用head作为新链表的头，这样如果我们不给定多余的指针，我们必须每次遍历一遍新链表才能得到尾的所在，所以我们在最开始也定义一个尾，这样就省去了每次遍历的麻烦。

     struct ListNode *cur1 = list1, *cur2 = list2;struct ListNode *head = NULL, *tail = NULL;

我们想要把比较过后的小的那个给到新的链表里面，所以进行判断，但是需要考虑初始情况，即head为空时，这时候head和tail都为空，我们需要判断，如果cur1-val小的话，需要

             if (head == NULL){head = tail = cur1;}

反之亦然。

随后中间逻辑就是尾插，

             else{tail->next = cur1;tail = cur1;}

通过使用cur->next给到cur1进行迭代。我们上面尾插是不改变cur1的下一个指向的，所以直接使用下列代码即可。

             cur1 = cur1->next;

最后，我们判断结束条件，应该是两个链表先遍历完一个即可。

 while (cur1 && cur2)

遍历完一个链表之后，只需要把另外一个链表追加到新链表的后面即可。

     if (cur1){tail->next = cur1;}else{tail->next = cur2;}

代码

 struct ListNode *mergeTwoLists(struct ListNode *list1, struct ListNode *list2){struct ListNode *cur1 = list1, *cur2 = list2;struct ListNode *head = NULL, *tail = NULL;if (cur1 == NULL)return cur2;if (cur2 == NULL)return cur1;while (cur1 && cur2){//比较if (cur1->val < cur2->val){if (head == NULL){head = tail = cur1;}//尾插else{tail->next = cur1;tail = cur1;}//迭代cur1 = cur1->next;}else{if (head == NULL){head = tail = cur2;}else{tail->next = cur2;tail = cur2;}cur2 = cur2->next;}}if (cur1){tail->next = cur1;}else{tail->next = cur2;}return head;}

优化

1. 1. 我们发现，每次进入循环都要判断head到底是否为空，不妨把这个拿到循环外面来，只要写一个判断语句即可，省去了后面每次都要判断的辛苦。

         if (cur1->val < cur2->val){head = tail = cur1;cur1 = cur1->next;}else{head = tail = cur2;cur2 = cur2->next;}

1. 2. 带哨兵位的链表。

带哨兵位就是说的是plist指向的头节点是不含值的节点，它的作用就是指向下一个节点，我们如果定义链表定义出带哨兵位的节点的话，就不需要传递二级指针，因为我们无须改变plist的值，而只是改变plist之后的指向。

哨兵位一般都是malloc出来的。

 head = tail = (ListNode*)malloc(sizeof(ListNode));

接下来我们需要做的就是往tail后面进行链接就可以了。

但是不能返回head了，因为head只是哨兵位，而且我们在最后的时候我们需要释放这个哨兵位的头。

我们应该先去储存哨兵位的下一位，也就是真正的头，随后free掉，然后返回新的头即可。

 struct ListNode* list = head->next;free(head);return list;

链表分割

现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。

思路

如果不要求保持原来的数据顺序，那我们就直接进行判断，小于x的头插，大于x的进行尾插就可以了。但是这个题目要求的是数据的顺序不变，那么我们需要转变策略，创建两个新链表，一个放大的，一个放小的，遍历一遍分好类之后，将二者合并即可。

但是贴到网站上进行提交时，发现超出内存了。一般内存超出了限制是因为程序编写不当，导致死循环从而引起的。仔细分析可以发现，bigger的最末节点仍旧指向着smaller的最末节点，导致整个链表在不断的死循环，这时候我们应该让bigger的末尾节点指向NULL。

代码

 ListNode *partition(ListNode *pHead, int x){ListNode *smaller = NULL, *bigger = NULL;ListNode *tails = NULL, *tailb = NULL;smaller = tails = (ListNode *)malloc(sizeof(ListNode));bigger = tailb = (ListNode *)malloc(sizeof(ListNode));ListNode *cur = pHead;while(cur){if(cur->val<x){//尾插到smaller里面去tails->next = cur;tails = cur;}else{tailb->next = cur;tailb = cur;}cur = cur->next;}tails->next = bigger->next;bigger->next = NULL;ListNode *lista = smaller->next;free(bigger);free(smaller);return lista;}

链表的回文结构

思路1

首先空间复杂度为1，我们就不能额外的创建新链表。初步考虑为，第一个和倒数第一个比较，第二个和倒数第二个比较，(找到第k个方法是知道的，我们只需要定义快慢指针，让快指针提前走k步即可，然后让快慢一起走到快指针为NULL即可)

但是经过编写之后发现太难实施。于是放弃这种思路。

思路2

找到中间节点(引用之前的函数)，让之后的逆置(引用之前的函数)，随后进行一一比较。

其中一个比较关键的点在于，如果我们这样编写， 中间节点的前一个节点的最终指向是逆置之后的整个链表的最后一个节点，分奇偶情况，如果是奇数情况，无需比较，因为前面的节点都可以一一对应，走到最后一个节点处，必然相等，程序继续运行，直接指向NULL，程序中止；如果是偶数情况，由于找中间节点时如果是偶数情况，我们找到的是中间两个节点中后面的那个节点，所以相比于前半段链表，后半段链表更先结束，前后段链表一一比较之后，后面指向NULL时，前半段的最后节点指向链表的最终节点，此时程序就中止了，所以不必考虑让前面的节点去指向空。

思路比较关键，代码非常简单，注意引用之前的两组代码，将他们作为接口函数使用。

输入两个链表，找出它们的第一个公共节点

链表相交只能是Y字形而非类似两根直线相交，这是因为一个节点只能有一个指向。（相交实际上就是指向同一个节点，需要比较的是地址）

实际上，题目分为两个部分：

1. 判断两个链表是否相交

2. 如果相交，找出起始相交节点。

错误思路

逆置两个链表，开始比较，找到第一个不同的节点，并返回这个节点的 前一个节点。

这是错误的，这是因为如果逆置，如图所示，我们不知道c1是到底指向a2还是指向b3，也就是说，我们先逆置A链表，后逆置B链表，则c1指向b3，反之亦然，无法判断。

思路1(暴力求解)

依次取A链表中的每个节点跟B链表中的所有节点比较，如果有地址相同的节点，就是相交，第一个相同的交点，就是相交节点。但是时间复杂度高O(N^2)，穷举。

思路2，优化到O(N)

1. 尾节点相同就相交，不相同就不相交。

2. • 可以看如果两个链表长度相同，由于其相交之后的长度是相同的，那么可以知道相交节点之前的长度也是相同的。我们就只需要设定两个指针，同时开始比较即可；

   • 如果两个链表长度不同，设其中A的长度为a，B的长度为b，相交节点之后的长度为x，则A需要走过(a-x)步才能找到相交节点，B需要走过(b-x)步才能找到相交节点。只需要先让长度较长的链表走过|a-b|步即可，这样会同时找到节点。

   • 所以我们只需要先判断链表的长度再按上述方法找相交即可。

逻辑分析

• 因为要找尾节点相同与否，所以至少都要从开头遍历一遍才可以。正好这样我们也可以顺便把两个链表的长度求出来。

 ListNode *tailA = headA, *tailB = headB;int lengthA = 1, lengthB = 1;//找尾巴，求长度while (tailA->next){tailA = tailA->next;lengthA++;}while (tailB->next){tailB = tailB->next;lengthB++;}

• 判断尾节点相同

     //不相交if(tailA != tailB){return NULL;}

• 因为我们后续的思路就是判断出A、B链表中较长的链表和较短的，所以我们可以先将其进行区分，如下、

 ListNode *longList = headA;ListNode *shortList = headB;if(lengthA < lengthB){ListNode *longList = headB;ListNode *shortList = headA;}

• 长的多走他们之间长度的差值步即可。

 //长的走abs步int gap = abs(lengthA - lengthB);while (gap--){longList = longList->next;}

• 判断是否相等，如果相等就是结束了。

     while(longList!=shortList){longList = longList->next;shortList = shortList->next;}return longList;

代码

下面的代码其中有一些多余的部分，是思考的部分

 struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB){ListNode *tailA = headA, *tailB = headB;int lengthA = 1, lengthB = 1;//找尾巴，求长度while (tailA->next){tailA = tailA->next;lengthA++;}while (tailB->next){tailB = tailB->next;lengthB++;}//不相交if(tailA != tailB){return NULL;}// ListNode* curA = headA;// ListNode* curB = headB;//可以使用绝对值函数//abs(lengthA - lengthB)​//下面这段函数太冗余了，完全是重复的代码，只是区分headA和headB//可以设定一个长的和短的，如下ListNode *longList = headA;ListNode *shortList = headB;if(lengthA < lengthB){ListNode *longList = headB;ListNode *shortList = headA;}//长的走abs步int gap = abs(lengthA - lengthB);while (gap--){longList = longList->next;}while(longList!=shortList){longList = longList->next;shortList = shortList->next;}return longList;// if (lengthA >= lengthB)// {//     int d = lengthA - lengthB;//     while (d--)//     {//         curA = curA->next;//     }//     while(curA)//     {//         if(curA->next == curB->next)//         {//             return curA->next;//         }//         curA = curA->next;//         curB = curB->next;//     }// }// else// {//     int d = lengthB - lengthA;//     while(d--)//     {//         curB = curB->next;//     }//     while(curB)//     {//         if (curA->next == curB->next)//         {//             return curA->next;//         }//         curA = curA->next;//         curB = curB->next;//     }// }}

本文标签： 数据结构基础经典面试Oj题单向链表经典Oj题目第一弹（做题思路加逻辑分析加代码实操，一应俱全的汇总）