数据结构初阶leetcodeOJ题（二）

目录

第一题

 思路：

第二题

 思路

 第三题

描述

示例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 herestruct 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;
}