反转链表
给你单链表的头节点 head ,请你反转链表,并返回反转后的链表
输入:head = [1,2,3,4,5]
输出:[5,4,3,2,1]
下面介绍两种思路,均能解决问题
1.改变节点指向
定义三个节点(==思考为什么定义三个而不是两个?==)而后通过指针遍历把cur指向的节点方向指向前一个,然后通过迭代到末尾,当cur为空退出循环
==代码实现如下==
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseList(struct ListNode* head)
{
if(head==NULL)
return NULL;
struct ListNode* prev=NULL;
struct ListNode* cur=head;
struct ListNode* next=head->next;
while(cur)
{
cur->next=prev;
prev=cur;
cur=next;
if(next)
next=next->next;
}
return prev;
}
2.将每一个节点都头插
是一个新方法,只需要把新创建一个头,然后把每一个节点都头插进来即可,下面为原理图
==代码实现如下==
struct ListNode* reverseList(struct ListNode* head)
{
struct ListNode* cur = head;
struct ListNode* rhead = NULL;
while (cur)
{
struct ListNode* next = cur->next;
//头插
cur->next = rhead;
rhead = cur;
//迭代
cur = next;
}
return rhead;
}
关于代码简洁性:
代码简洁程度取决于特殊情况的处理,例如,假设这里把next定义在while循环外,那么假设参数为NULL,就需要对特殊情况做处理,此时代码就多了if条件,整体来说简洁程度就降低了
简洁程度需要对特殊情况的处理足够好,才能足够精炼解决问题
链表的中间节点
给你单链表的头结点 head ,请你找出并返回链表的中间结点。
如果有两个中间结点,则返回第二个中间结点。
1.遍历链表求长度
==代码实现如下==
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* middleNode(struct ListNode* head)
{
struct ListNode* plist=head;
int flag=0;
while(plist)
{
while(plist->next!=NULL)
{
plist=plist->next;
flag++;
}
break;
}
flag+=1;
flag=flag/2+1;
for(int i=1;i<flag;i++)
{
head=head->next;
}
return head;
}
2.快慢指针法
定义两个指针,一个指针是慢指针,每次走一步;一个指针是快指针,每次走两步。当快指针走到末尾时,慢指针走的位置恰好为整个链表的一半
相比起思路1来说,时间复杂度只是O(N),从时间复杂度来讲,这个方法更优
具体实现原理如下图所示
==代码实现如下==
struct ListNode* middleNode(struct ListNode* head)
{
struct ListNode* slow=head;
struct ListNode* fast=head;
while(fast!=NULL && fast->next!=NULL)
{
slow=slow->next;
fast=fast->next->next;
}
return slow;
}
链表中倒数第K个节点
描述
输入一个链表,输出该链表中倒数第k个结点。
输入:1,{1,2,3,4,5}
输出:{5}
1.遍历求长度,根据k求结果
代码思路和上题十分类似,十分简单
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
/**
*
* @param pListHead ListNode类
* @param k int整型
* @return ListNode类
*/
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
// write code here
struct ListNode* cur=pListHead;
struct ListNode* prev=pListHead;
int flag=0;
while(cur)
{
cur=cur->next;
flag++;
}
if(k>flag)
{
return NULL;
}
for(int i=0;i<flag-k;i++)
{
prev=prev->next;
}
return prev;
}
2.仿照上题,快慢指针的方法解决
和上题相比,略有不同的一点是,上面的快指针每次走的是一样的,而对于这个题来说,假设K=4,那么就令快指针每次走四格,其余思路和上题类似
总结原理:这里既然要求的是倒数第k个,那么就令fast指针和slow指针之间差k个,然后两个一起走,当fast指针到末尾的时候,slow所在的位置就是fast位置减去它们一开始的距离差,也就是倒数k个的位置
整体思路是十分巧妙的,其实原理和方法1类似,都是找到最后一个元素,然后再找前面倒数的元素,但相比起来使用快慢指针的方法可以让时间复杂度缩短到最少
==代码实现如下==
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
struct ListNode* fast=pListHead;
struct ListNode* slow=pListHead;
for(int i=0;i<k;i++)
{
if(fast)
fast=fast->next;
else
return NULL;
}
while(fast)
{
fast=fast->next;
slow=slow->next;
}
return slow;
}
这里思考
第一次走k步和走k-1步有什么区别?