练习题

• 1.移除链表元素(LeetCode203)
• 2.链表的中间结点(LeetCode876)
• 3.链表的倒数第k个结点(剑指offer)
• 4.反转链表(LeetCode206)
• 5.合并两个有序链表(LeetCode21)
• 6.链表分割(牛客)
• 7.链表的回文结构(牛客)

1.移除链表元素(LeetCode203)

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

思路
创建一个新链表，把不等于val的结点尾插到新链表。

代码

struct ListNode 
{int val;struct ListNode* next;	
};
struct ListNode* removeElements(struct ListNode* head, int val)
{struct ListNode* NewHead = NULL;//创建一个新的头结点struct ListNode* cur = head;//用来遍历整个链表struct ListNode* tail = NULL;//指向新链表的最后一个结点，用来尾插数据while (cur){if (cur->val == val)//相等就把这个结点释放{struct ListNode* tmp = cur->next;//储存下一个结点的地址，防止节点释放后找不到下一个结点free(cur);cur = tmp;}else{if (NewHead == NULL)//将头结点指向不等于val的第一个元素{NewHead = tail = cur;}else{tail->next = cur;//尾插新结点tail = tail->next;//指向新链表的最后一个结点}cur = cur->next;}}if (tail)//如果最后一个结点刚好是val，那就tail指向的下一个结点置为NULL{        //如果链表是空，也不会进行对NULL的访问tail->next = NULL;}return NewHead;
}

结果

2.链表的中间结点(LeetCode876)

给你单链表的头结点 head ，请你找出并返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。OJ链接

思路
常规思路就是遍历整个链表，得到链表的结点个数从而得到中间结点的下标，再遍历链表找到并返回这个结点。但在介绍一个牛逼的方法：快慢指针，慢指针每次循环走一步，快指针每次循环走两步，最终如果链表长度是奇数，快指针指向链表的最后一个结点，慢指针刚好指向中间结点，如果链表长度是偶数，快指针指向最后一个结点指向的NULL，慢指针指向两个中间结点的第二个结点。
代码

struct ListNode 
{int val;struct ListNode* next;
};
struct ListNode* middleNode(struct ListNode* head) 
{struct ListNode* slow = head, * fast = head;while (fast != NULL && fast->next != NULL)//用&&是因为只要有一个不满足就停止循环{slow = slow->next;fast = fast->next->next;}return slow;
}

结果

3.链表的倒数第k个结点(剑指offer)

输入一个链表，输出该链表中倒数第k个结点。OJ链接

思路
还是用快慢指针的方法。要求倒数第k个，快指针就先走k步，此时快指针和慢指针之间的距离为k步，然后和满指针每次走一步，当快指针指向NULL，慢指针和快指针的距离是k步，慢指针和最后一个结点的距离是k-1步，慢指针刚好是倒数第k个结点。
代码

struct ListNode 
{int val;struct ListNode* next;
};
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k) {struct ListNode* slow, * fast = NULL;slow = fast = pListHead;while (k--)//fast先走k步{if (fast == NULL)//走出链表，就直接返回NULL{return NULL;}fast = fast->next;}//此时fast与slow的距离是k，当fast指向NULL，//slow与最后一个节点的距离就是k-1,slow就是倒数第k个while (fast){slow = slow->next;fast = fast->next;}return slow;
}

结果

4.反转链表(LeetCode206)

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

思路
法1利用三个指针（n1，n2，n3）实现逆序，n2指向当前结点，n3指向下一个结点，n1指向上一个结点。如图。

法2创建一个新的链表，取出要逆序链表的节点头插到新链表。

代码

//法1
struct ListNode 
{int val;struct ListNode* next;};
struct ListNode* reverseList(struct ListNode* head)
{if (head == NULL)//检查是否为空{return NULL;}struct ListNode* n1 = NULL,*n2 =head,*n3 =head->next;while (n2)//一旦n2指向NULL就停止循环{n2->next = n1;n1 = n2;n2 = n3;if (n3)//防止n3越界访问，一旦n3指向NULL，就不再改变{n3 = n3->next;}}return n1;
}

//法2
struct ListNode 
{int val;struct ListNode* next;};
struct ListNode* reverseList(struct ListNode* head)
{struct ListNode* newHead = NULL;struct ListNode* cur = head;//遍历链表while (cur){struct ListNode* next = cur->next;//记住下一个结点cur->next = newHead;//指向头结点指向的结点newHead = cur;cur = next;}return newHead;//不用检查链表为空，因为为空不进入循环，返回NULL
}

结果

5.合并两个有序链表(LeetCode21)

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。OJ链接
思路
创建一个新链表，以此比较两个升序链表的结点，取小的结点尾插。如图。
代码

struct ListNode 
{int val;struct ListNode* next;};
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{struct ListNode* cur1 = list1, * cur2 = list2;//分别遍历两个链表struct ListNode* head = NULL,*tail = head;//head是新链表的头结点，tail指向新链表的最后一个结点，方便尾插if (list1 == NULL)//如果有链表为空，返回另一个链表{return list2;}if (list2 == NULL){return list1;}while (cur1 && cur2)//有一个是NULL就结束循环{if (cur1->val < cur2->val){if (head == NULL)//考虑到第一次插入节点{head = tail = cur1;}else{tail->next = cur1;tail = tail->next;cur1 = cur1->next;//cur1还指向原来链表的下一个结点，所以不用用指针记录下一个结点}}else{if (head == NULL)//考虑到第一次插入节点{head = tail = cur2;}else{tail->next = cur2;tail = tail->next;cur2 = cur2->next;//cur1还指向原来链表的下一个结点，所以不用用指针记录下一个结点}}}if (cur1 == NULL)//说明list2还有结点，直接插到新链表的尾部即可{tail->next = cur2;}if (cur2 == NULL){tail->next = cur1;}return head;
}

结果

6.链表分割(牛客)

现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。OJ链接
思路
把小于x的结点插到一个链表，大于或等于x的结点插到另一个链表，然后把两个链表链接起来。
预备知识
在使用单链表时，我们通常用用一个指针指向第一个结点，作为头结点，而这道题得使用哨兵位的头结点，用一个结点来指向链表的第一个结点。什么是哨兵位的头结点？顾名思义就是一个结点，这个结点不存储数据，只指向第一个结点，至于它的作用后面会讲到，现在只需知道它是一个不存储数据的、指向第一个结点的结点。

代码

struct ListNode {int val;struct ListNode* next;
};
struct ListNode* partition(struct ListNode* pHead, int x)
{struct ListNode* smallGuard = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* bigGuard = (struct ListNode*)malloc(sizeof(struct ListNode));smallGuard->next = NULL;bigGuard->next = NULL;struct ListNode* smallTail = smallGuard, * bigTail = bigGuard, * cur = pHead;while (cur){if (cur->val < x){smallTail->next = cur;smallTail = smallTail->next;}else{bigTail->next = cur;bigTail = bigTail->next;}cur = cur->next;}smallTail->next = bigGuard->next;//将大链表链接到另一个链表，bigTail->next = NULL;//同时记得将大链表的最后一个节点指向NULL，防止其指向链表的另一个节点，导致环形链表pHead = bigGuard->next;//将新链表的头节点赋值给phead，因为哨兵位的头节点要释放free(bigGuard);free(smallGuard);bigGuard = NULL;smallGuard = NULL;return pHead;
}

结果

哨兵位头节点的作用

7.链表的回文结构(牛客)

对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。

思路
先找到中间节点（可以用前面的函数），从中间节点开始，对后半段进行逆序（用前面的函数），最后判断前半段和后半段是否相等。

代码

struct ListNode {int val;struct ListNode* next;
};
struct ListNode* middleNode(struct ListNode* head) {struct ListNode* slow, * fast;slow = fast = head;while ((fast != NULL) && (fast->next != NULL)) {slow = slow->next;fast = fast->next->next;}return slow;
}
struct ListNode* reverseList(struct ListNode* head) {struct ListNode* newHead = NULL;struct ListNode* cur = head;while (cur) {struct ListNode* next = cur->next;cur->next = newHead;newHead = cur;cur = next;}return newHead;
}
bool chkPalindrome(struct ListNode* head)
{struct ListNode* mid = middleNode(head);struct ListNode* rhead = reverseList(head);while (rhead && head)//当有偶数个节点时，rhead先遇到NULL，当有奇数个节点时，head和rhead同时遇到NULL{if (rhead->val != head->val){return false;}}return true;
}

结果