数据结构链表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
    }

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