目录
第一题
思路:
第二题
思路
第三题
描述
示例1
思路
总结:这种类似的题,都是用快慢指针,相差一定的距离然后输出慢指针。
第一题
给你一个链表的头节点
head
和一个整数val
,请你删除链表中所有满足Node.val == val
的节点,并返回 新的头节点 。示例 1:
输入:head = [1,2,6,3,4,5,6], val = 6 输出:[1,2,3,4,5]示例 2:
输入:head = [], val = 1 输出:[]示例 3:
输入:head = [7,7,7,7], val = 7 输出:[]
方法一
思路:
快慢指针:一个指向目标结点,一个指向目标结点的前驱结点。用一个tmp保存pos->next.
free()掉目标结点。
分两种情况:如果只有一个节点或者要删除的结点是首元节点,那么这时pre为NULL,pos 指向pos;否则pre->next == pos;
struct ListNode* removeElements(struct ListNode* head, int val) {
struct ListNode* pre = NULL;
struct ListNode* pos = head;
while(pos!=NULL)
{
if(pos->val==val){
struct ListNode* tmp = pos->next;
free(pos);
pos = tmp;
if(pre==NULL){
head = pos;
}else{
pre->next = pos;
}
}
else
{
pre = pos;
pos = pos->next;
}
}
return head;
}
方法二:
思想;
创建新链表,用尾插法,尾插法没有改变原指针的next指向所以不用保存next节点,
但是在free()时要保存下一节点。
struct ListNode* removeElements(struct ListNode* head, int val)
{
struct ListNode* cur = head;
struct ListNode* newhead = NULL;
struct ListNode* tail = NULL;
while(cur!=NULL)
{
if(cur->val!=val)
{
if(newhead==NULL){
newhead = tail = cur;
}else{
tail->next = cur;
tail = cur;
}
cur = cur->next;
}else{
struct ListNode* tmp = cur ->next;
free(cur);
cur = tmp;
}
}
if(tail)
tail->next=NULL;
return newhead;
}
第二题
给你单链表的头结点
head
,请你找出并返回链表的中间结点。如果有两个中间结点,则返回第二个中间结点。
示例 1:
输入:head = [1,2,3,4,5] 输出:[3,4,5] 解释:链表只有一个中间结点,值为 3 。示例 2:
输入:head = [1,2,3,4,5,6] 输出:[4,5,6] 解释:该链表有两个中间结点,值分别为 3 和 4 ,返回第二个结点。
思路
用快慢指针:快指针一次走两个,慢指针一次走一个。这样他们的路程之间差二倍。所以输出慢指针,即输出中间节点。
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个结点。
示例1
输入:
1,{1,2,3,4,5}复制返回值:
{5}
思路
用快慢指针:快指针比慢指针先走k步,然后两者在同时走。
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
// write code here
struct ListNode* pre =pListHead;
struct ListNode* pos = pListHead;
while(k--){
if(pos!=NULL){
pos = pos->next;
}else{
return NULL;
}
}
while(pos!=NULL){
pre = pre->next;
pos = pos->next;
}
return pre;
}
总结:这种类似的题,都是用快慢指针,相差一定的距离然后输出慢指针。
第四题
给你单链表的头节点
head
,请你反转链表,并返回反转后的链表。示例 1:
输入:head = [1,2,3,4,5] 输出:[5,4,3,2,1]示例 2:
输入:head = [1,2] 输出:[2,1]示例 3:
输入:head = [] 输出:[]提示:
- 链表中节点的数目范围是
[0, 5000]
-5000 <= Node.val <= 5000
进阶:链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题?
方法一
将节点之间的next翻转。
用三个指针的原因是,只用两个指针翻转时,会导致链表断裂,但是用第三个指针保存下一个节点这样链表就不会断裂。
/**
* 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* left = NULL;
struct ListNode* right= head;
struct ListNode* tmp = head->next;
while(right!=NULL)
{
right->next = left;
left = right;
right = tmp;
if(tmp!=NULL)
tmp = tmp->next;
}
return left;
}
方法二
用头插法,注意头插法需要保存指针。尾插法不用保存指针。
错误总结
(1)注意头插是新结点指向头结点,然后在将新节点设置为头结点。而不是直接将新节点设置为头节点
(2)C语言赋值语句,左值是变量,将新节点设置为头结点。newnode = cur;这是头结点为cur
//方法二
struct ListNode* reverseList(struct ListNode* head)
{
if(head==NULL)
return NULL;
struct ListNode* cur = head;
struct ListNode* newhead = NULL;
while(cur!=NULL)
{
struct ListNode* next = cur ->next; //保存下一个
cur->next = newhead;
newhead = cur;
cur = next;
}
return newhead;
}