数据结构链表2（常考习题1）（C语言）

移除链表元素：

. - 力扣（LeetCode）

题目：

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

解题思路：

情况1：

情况2：

情况3：

我们以第一种情况写代码：

ListNode* removeElements(ListNode* head, int val)
{ListNode* cur = head;ListNode* slow = head;while (cur){if (cur->val == val){ListNode* tmp = cur->next;free(cur);cur = tmp;slow->next = cur;}else{slow = cur;cur = cur->next;}}
}

以第二、三种特殊情况改代码：

如果第一次就要删除头：

struct ListNode* removeElements(struct ListNode* head, int val)
{struct ListNode* cur = head;struct ListNode* tmp = NULL;struct ListNode* slow = head;while (cur){if (cur->val == val){tmp = cur->next;if(head->val == val){free(cur);cur = tmp;head = cur;slow = head;}else{free(cur);cur = tmp;slow->next = cur;}}else{slow = cur;cur = cur->next;}}return head;
}

反转链表：

. - 力扣（LeetCode）

题目：

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

解题思路：

考虑特殊：

只有一个元素：

同样适用！！ 

        双指针解题，一个前驱指针，一个指向head的指针，还有一个临时变量next为了记录head的next的值。

具体代码如下：

ListNode* reverseList(ListNode* head)
{ListNode* cur = head;ListNode* slow = NULL;ListNode* next = NULL;while (cur){next = cur->next;cur->next = slow;slow = cur;cur = next;}
}

链表的中间节点：

. - 力扣（LeetCode）

题目：

        给你单链表的头结点 head ，请你找出并返回链表的中间结点。

        如果有两个中间结点，则返回第二个中间结点。

解题思路：

        利用快慢指针，有四种情况，如图所示：

第一种，链表个数为偶数时：

第二种，链表个数为奇数时：

第三种，链表个数为1个时：

第四种，链表个数为2个时：

综上：

得出结论：
1、当链表个数大于2时，且为偶数时：

当快指针的next走到NULL时，慢指针所在的地方就是中间结点的地方。

2、当链表个数大于2时，且为奇数时：

当快指针走到NULL时，慢指针所在的地方就是中间节点的地方。

3、当链表个数等于1时：

快指针和慢指针不需要走。

4、当链表个数为2时：

和情况一是一样的。

综上：

也就是快指针分两种情况：

第一种就是快指针自身到达NULL时，第二种就是快指针的next到达NULL时。

不论是那种情况，最终都返回慢指针！！

代码如下：

ListNode* middleNode(ListNode* head) 
{ListNode* fast = head;ListNode* slow = head;while (fast){if (fast->next == NULL){return slow;}fast = fast->next->next;slow = slow->next;}return slow;
}

合并两个有序链表：

. - 力扣（LeetCode）

题目：

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

解题思路：

        两个链表，每个链表都有一个可以移动的指针，接着让一个指针移动，每移一步让两个指针指向的值做对比，小的移下来，然后让新链表的指针和刚刚移动过的俩把表指针往后走一步。

        直到其中一个链表的指针指向空之后，将另一个链表的剩下部分整体移过去！

画图很重要！！！

特殊考虑：

        如果其中一个链表为空，可以指直接返回另一个链表的地址！

代码如下：

画图很重要！！！！！！

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{struct ListNode* cur1 = list1;struct ListNode* cur2 = list2;struct ListNode* newhead = NULL;struct ListNode* tmp = NULL;if (cur1 == NULL){return cur2;}else if(cur2 == NULL){return cur1;}while (cur1 && cur2){if (cur1->val > cur2->val){if (newhead == NULL){newhead = tmp = cur2;}else{tmp->next = cur2;tmp = tmp->next;}cur2 = cur2->next;}else{if (newhead == NULL){newhead = tmp = cur1;}else{tmp->next = cur1;tmp = tmp->next;}cur1 = cur1->next;}}if (cur1 == NULL){tmp->next = cur2;}else{tmp->next = cur1;}return newhead;   
}

链表分割：

链表分割_牛客题霸_牛客网

题目：

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

解题思路：

        将比x大的和比x小的首先区分开，最后再将其合并在一起！！

注意：最后比x大的后面需要手动在末尾添加NULL指针！

考虑特殊：

        如果链表中没有比x大的数，或者没有比x小的数，此时直接返回原链表的地址！！

代码如下：
 

ListNode* partition(ListNode* pHead, int x) 
{ListNode* cur = pHead;ListNode* newhead1 = NULL;ListNode* tmp1 = NULL;ListNode* newhead2 = NULL;ListNode* tmp2 = NULL;while (cur){if (cur->val > x){if (newhead1 == NULL){newhead1 = tmp1 = cur;}else{tmp1->next = cur;tmp1 = tmp1->next;}}else{if (newhead2 == NULL){newhead2 = tmp2 = cur;}else{tmp2->next = cur;tmp2 = tmp2->next;}}cur = cur->next;}if (!(newhead1 && newhead2)){return pHead;}tmp1->next = NULL;tmp2->next = newhead1;return newhead2;
}

链表的回文结构：

链表的回文结构_牛客题霸_牛客网

题目：

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

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

测试样例：

1->2->2->1

返回：true

解题思路：

        文字叙述：

        只需要将该链表进行反转后，然后两个链表进行遍历，如果中途有不一样的值就输出fasle

如果遍历结束后，两个指针都指向NULL，返回true，就可以说明该链表是回文结构。

具体代码：
        

     ListNode* Reverse(ListNode*head)//链表反转代码
{ListNode* cur = head;ListNode* slow = NULL;while (cur){ListNode* tmp = cur->next;cur->next = slow;slow = cur;cur = tmp;}return slow;
}bool chkPalindrome(ListNode* pHead) //判断回文代码{ListNode* cur = pHead;ListNode* newhead = NULL;newhead = Reverse(cur);while (cur&&newhead){if(cur->val != newhead->val){return false;}cur = cur->next;newhead = newhead->next;}return true;// write code here}

！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！