链表OJ题+牛客题

目录

206.反转链表

876.链表的中间节点

链表中倒数第k个节点

CM11链表分割

OR36 链表的回文

---

206.反转链表

给你单链表的头节点head,请你反转链表，并返回反转后的链表。

 实现如下结果：

        

 思路：

取链表中的节点头插：

代码：

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* reverseList(struct ListNode* head){ struct ListNode *cur=head; struct ListNode *plist=NULL; while(cur) { struct ListNode *next=cur->next; cur->next=plist;//cur->next指向plist的地址 plist=cur; //plist 指向cur的地址，刚上面的一行代码和这一行代码使得链表的空间相连 cur =next; } return plist; }/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* reverseList(struct ListNode* head){ struct ListNode *cur=head; struct ListNode *plist=NULL; //作为新的头节点 while(cur) { struct ListNode *next=cur->next; //记住cur的下一个节点 cur->next=plist;// 头插 plist=cur; //换头 cur =next; //将原来cur->next节点的地址赋给cur } return plist; } 876.链表的中间节点

给定一个头节点为head的非空单链表，返回链表的中间节点。如果有两个中间节点，则返回第二个中间节点。要求只能遍历一遍

思路：用快慢指针找到中间节点，定义两个结构体变量指针slow,fast。

slow每次走一步，fast每次走两步。当fast->next为空的时候,则链表长度为奇数,那么slow就是中间节点；当fast为空时，链表的长度为偶数，那么中间节点有两个，则返回第二个中间节点。

代码：

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* middleNode(struct ListNode* head){ struct ListNode *fast,*slow; slow=fast=head; while(fast&&fast->next) { slow=slow->next; fast=fast->next->next; } return slow; } 链表中倒数第k个节点

输入一个链表，输出该链表中第k个节点

思路：定义结构体指针变量slow,fast,让fast先走k部,然后它们都各自每次向后走一步，当fast为空的时候，返回slow,此时slow就为链表中第k个节点。也可以让fast先走k-1步，当fast->next为空的时候，slow就是链表中第k个节点。

在这里需要注意的就是要注意k的值是否大于链表的长度，如果大于则返回NULL.

 代码：

struct ListNode*FindKthToTail(struct ListNode*pListHead,int k) { struct ListNode*fast,slow; fast=slow=pListHead; while(k--)//让fast先走k步 { //链表可能没有k步长 if(fast==NULL) { return NULL; } fast=fast->next; } while(fast)//当fast为空 { fast=fast->next; slow=slow->next; } return slow; } CM11链表分割

描述：

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

思路：

这道题用带哨兵位的链表求解，将所有小于x的节点尾插到第一个哨兵位节点后面；其余的尾插到第二个带哨兵位节点后面；最后将两个链表链接，返回第一个哨兵位节点后一个节点。

这里需要注意的是，在最后尾插结束时记得将第二个链表的尾节点的下一个节点置空（即上图的greaterTail的下一个节点置空），因为尾插结束，greaterTail->next还指向链表中的其他节点，如果不置空，会形成环。

 

代码： 

class Partition { public: ListNode *Partition(ListNode*pHead,int x) { struct ListNode*lessHead,*lessTail; struct ListNode*greaterHead,*greaterTail; lessHead=lessTail=(struct ListNode*)malloc(sizeof(structListNode)); greaterHead=greaterTail=(struct ListNode*)malloc(sizeof(struct ListNode)); lessTail->next=greaterTail->next=NULL; struct ListNode*cur=pHead; while(cur) { if(cur->val<x) { lessTail->next=cur; lessTail=lessTail->next; } else { greaterTail->next=cur; greterTail=greaterTail->next; } cur=cur->next; } lessTail->next=greaterHead->next; greaterTail->next=NULL; pHead=lessHead->next; free(lessHead); free(greaterHead); return pHead; } } OR36 链表的回文

描述：

对于一个链表，请设计时间复杂度为O(n),空间复杂度为O(1)的算法，判断其是否为回文结构。

给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900.

 思路：将链表的后半部分的节点逆置，再将前半部分的值和后半部分的值相比。因为额外的空间复杂度为O(1)，所以不能整体逆置，整体逆置要重新开辟一个和原来一样长的链表空间。所以这里将后半部分的节点逆置之后就可以比较了。

代码：

/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) {} };*/ class PalindromeList { public: struct ListNode* middle(struct ListNode* phead) //返回中间值 { struct ListNode*fast,*slow; fast=slow=phead; while(fast&&fast->next) { slow=slow->next; fast=fast->next->next; } return slow; } struct ListNode*reverse(struct ListNode*phead) { struct ListNode*cur=phead; struct ListNode*rehead=NULL; while(cur) { struct ListNode*next=cur->next; //头插 cur->next=rehead; rehead=cur; cur=next; } return rehead; } bool chkPalindrome(ListNode* A) { struct ListNode*mid=middle(A); struct ListNode*rehead=reverse(mid); while(A && rehead) { if(A->val!=rehead->val) return false; A=A->next; rehead=rehead->next; } return true; // write code here } };