前言

题目一：链表的中间节点

思路

分析

题解

题目二：链表中倒数第k个结点

思路

分析

题解

题目三：合并两个有序链表

思路

分析

题解

方法二

题解

题目四：链表的回文结构

思路

分析

题解

总结

前言

今天我将开启一个新的专栏，数据结构与算法刷题训练营，题目从基础简单题目开始逐步进阶，以便于初学者巩固和运用所学的知识。

题目一：链表的中间节点

题目描述：

示例与提示：

题目链接

链表的中间节点https://leetcode.cn/problems/middle-of-the-linked-list/description/

思路

题目中的链表属于单链表，我们要怎么计算中间节点呢？先遍历一遍链表统计链表节点个数，然后计算出中间节点，再遍历到需要返回的节点。这或许是大多数人能想到的方法。但是这种方法效率太低。今天我向大家介绍一种新的做题思路，这种方法在其他题目中也是适用。

快慢指针法：

我们可以创建两个指针，一个快指针一次走两步，一个慢指针一次走一步。当快指针走到尾时，返回慢指针就是中间节点。

分析

情况一：

节点为奇数个。

假设节点有5个，那需要返回的节点就是第3个节点。初始时，两指针都指向第一个节点，慢指针一次走一步，快指针一次走两步。执行一次情况如上图。当快指针走到最后一个节点时就要结束如下图：

情况二：

节点为偶数个。

这是已经执行两次后的状态，接下来fast指针继续走：

fast指向NULL，而slow指向要返回的节点。

题解

了解完整体思路，我们依据分析中的情况进行编写代码：

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

题目二：链表中倒数第k个结点

题目描述：

题目链接

倒数第k个节点https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tpId=13&&tqId=11167&rp=2&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking

思路

这道题目依然可以使用快慢指针的方法来寻找倒数第k个节点。先让快指针走k步，然后让两指针同时向后移动，知道快指针遍历完链表结束。

分析

初始情况下，两指针都指向第一个节点，先让fast指针走k步：

我们假设要找倒数第3个节点，fast走3步就指向了第四个节点。

然后两指针开始同时移动：

当fast指针指向NULL时就结束，此时slow指向的就是倒数第k个节点。

题解

根据上述的分析，我们进行编写代码：

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {struct ListNode* fast=pListHead,*slow=pListHead;for(int i=0;i<k;i++){if(fast==NULL){return NULL;}fast=fast->next;}while(fast){fast=fast->next;slow=slow->next;}return slow;
}

在代码实现时要注意特殊情况，如果链表为NULL或者k大于链表长度，传进来就要进行特殊处理。

题目三：合并两个有序链表

题目描述：

示例：

题目链接：

合并两个有序链表https://leetcode.cn/problems/merge-two-sorted-lists/description/

思路

题目中给的是升序数组，解题思路就是比较链表元素，取小的进行尾插。思路较为简单。

分析

接下来我们对整体规划进行分析假设初始时：

把一个链表的元素插入到另一个链表这样操作太麻烦，所以我们可以重新创建一个头指针，将两个链表上的节点插入到新的链表中，创建新链表时，初始化头和尾都为NULL。

然后进行比较，第一步两个大小相同，任取一个插入：

然后再拿着list2中的第一个节点与list1节点进行比较，插入：

以此类推不断进行比较尾插。

结束条件就是一个链表为NULL结束

最后将剩余节点的链表尾插到新链表中，返回新链表的头。

题解

理解了思路就根据分析的内容进行编写代码：

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{if(list1==NULL)                //考虑原链表中有空链表的情况。return list2;if(list2==NULL)return list1;struct ListNode* head=NULL,*tail=NULL;while(list1&&list2){if(list1->val > list2->val)//比较大小取小的尾插{if(head==NULL)         //考虑特殊情况新建链表为NULL时进行特殊处理{tail=head=list2;}else                   //尾插{tail->next=list2;tail=tail->next;}list2=list2->next;    //尾插后继续向后}else{if(head==NULL){tail=head=list1;}else{tail->next=list1;tail=tail->next;}list1=list1->next;}}if(list2==NULL)            //一个链表为NULL时将另一个链表剩余的节点尾插到新链表。tail->next=list1;elsetail->next=list2;return head;
}

虽然思路非常简单，但是代码实现却很不容易，需要很多要考虑的特殊情况。

方法二

和思路一相同，也是比较大小，将小的尾插到新的链表。但是可以使用带头结点的链表，这样再插入时就不需要考虑新链表为NULL时的情况，进行特殊处理。可以更好的简化代码。

题解

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{if(list1==NULL)return list2;if(list2==NULL)return list1;struct ListNode* head=NULL,*tail=NULL;head=tail=(struct ListNode*)malloc(sizeof(struct ListNode));while(list1&&list2){if(list1->val > list2->val){tail->next=list2;tail=tail->next;list2=list2->next;}else{tail->next=list1;tail=tail->next;list1=list1->next;}}if(list2==NULL)tail->next=list1;elsetail->next=list2;struct ListNode* del=head;head=head->next;free(del);return head;
}

注意：原链表中不带头节点，返回时不能返回头节点，需要将头节点释放掉，返回头节点的下一个节点。

题目四：链表的回文结构

题目描述：

题目链接：

链表的回文结构https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa?tpId=49&&tqId=29370&rp=1&ru=/activity/oj&qru=/ta/2016test/question-ranking

思路

有人可能会想，这不很简单吗？把这个链表反转一下，再和原链表数据依次比较不就解决了，但是这里注意题目要求。

题目要求时间复杂度为O(N)，空间复杂度为O(1)，上述思路需要将原链表复制一份后才可以与逆置是链表进行比较，空间复杂度为O(N)。

这道题的思路是这样的，可以先找到链表的中间节点，然后从中间节点开始，对后部分的链表进行逆置，然后从中间开始与开头的节点对比，看两个值是否相同。

分析

情况一：

节点为偶数个，把后半部分节点逆置，然后依次比较，这里注意其实前半部分的2节点的next这时依然指向的是后半部分的2，后半部分的2节点的next指向NULL。如下图：

逆置之后，返回的是后半部分1节点的地址，然后进行遍历，直到为NULL结束。

情况二：

节点数量为奇数个

实际情况和上述一样：

但这里在比较的时候就要注意一下3节点，这里不需要把前半部分2节点的next置为NULL，当遍历到最后时，都遍历到了3节点一定是相同的

题解

当然这些逆置、找中间节点的接口我们已经写过了，可以CV一下前边的代码，这样写代码还是很舒服的Ctrl+C、Ctrl+V

当然借此我再介绍一种新的逆置链表的方法，我们可以使用头插来实现链表逆置。将原链表的节点依次头插到新的节点，这样就轻松实现了逆置。

代码如下：

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

整体题解：

class PalindromeList {
public:
struct ListNode* reverseList(struct ListNode* head)
{struct ListNode* cur=head;struct ListNode* newhead=NULL;while(cur){struct ListNode* next=cur->next;cur->next=newhead;newhead=cur;cur=next;}return newhead;
}struct ListNode* middleNode(struct ListNode* head)
{struct ListNode* fast=head,*slow=head;while(fast && fast->next){slow=slow->next;fast=fast->next->next;}return slow;
}bool chkPalindrome(ListNode* A) {struct ListNode* mid=middleNode(A);//中间节点struct ListNode* rmid=reverseList(mid);//反转后的中间节点while(A && rmid)    {if(A->val!=rmid->val){return false;}else{rmid=rmid->next;A=A->next;}}return true;}
};