程序员进阶之算法练习（五十）LeetCode链表专题
正文
链表是面试中经常考察的概念，选了4道LeetCode中常见链表题目，难度是Easy和Medium。
1.移除链表第n个节点
题目链接 题目大意： 给出一个链表，删除链表的倒数第n个节点，然后返回链表的头指针。 Example: 给出链表 1->2->3->4->5, and n = 2. 操作后的链表 1->2->3->5.
题目解析： 这里可以分解两个子问题： 1、找到链表倒数第n个点； 2、在链表中删除一个节点；
问题1可以先遍历指针得到节点个数sum，这样可以得到删除的节点为正数的第sum-n+1个节点； 问题2是标准问题，注意next指针的特殊处理；
这里有个trick，如果删除的节点是第一个节点，此时应该返回head->next的节点； 其他情况，类似 1->3->x->4->6，这样的链表，删除中间x点，只需要找到x的上一个节点，使得其next等于x的下一个节点即可。
复杂度解析： 时间复杂度是O(N) 空间复杂度是O(N)
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode *tmp = head;
int count = 1;
while (tmp->next) {
tmp = tmp->next;
++count;
}
int x = count - n + 1;
ListNode *ret = head;
if (x == 1) {
ret = head -> next;
}
else {
tmp = head;
while (x > 2) {
--x;
tmp = tmp->next;
}
if (tmp->next) {
tmp->next = tmp->next->next;
}
else {
tmp->next = NULL;
}
}
return ret;
}
};2.合并两个有序链表
题目链接 题目大意： 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例： 输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4
题目解析： 遍历两个链表，每次从链表中选择一个较小大数字的节点出来，直接两个链表为空； 注意：需要考虑两个链表，部分为空或者全部为空的情况；
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode *ret = NULL, *cur = NULL;
while (l1 && l2) {
if (l1->val < l2->val) {
if (!cur) {
cur = ret = l1;
}
else {
cur->next = l1;
}
cur = l1;
l1 = l1->next;
}
else {
if (!cur) {
cur = ret = l2;
}
else {
cur->next = l2;
}
cur = l2;
l2 = l2->next;
}
}
if (l1) {
if (cur) {
cur->next = l1;
}
else {
ret = cur = l1;
}
}
else {
if (cur) {
cur->next = l2;
}
else {
ret = cur = l2;
}
}
return ret;
}
}leetcode;3.两两交换链表中的节点
题目链接 题目大意： 给出一个链表，要求每两个节点做一次节点交换，如果是奇数链表，最后一个节点不用交换； 比如说给出1->2->3->4，要求结果是2->1->4->3； 要求： 1、常数的空间大小； 2、不允许修改链表节点的值，只能修改其next指针；
示例 1：
输入：head = [1,2,3,4] 输出：[2,1,4,3]
示例 2： 输入：head = [] 输出：[]
示例 3： 输入：head = [1] 输出：[1]
题目解析： 假如是数组交换，那么就是a[1]=a[2]这样直接交换即可； 如果允许值修改，同样可以用上面的方案，但这里要求交换节点；
先看直接交换节点的情况：对于节点1和2，直接交换next指针，变成2，1，此时链表是2->1->3->4->NULL; 接着重复上面的过程交换3，4，变成4，3，链表是4->3->NULL，但是此时链表并不是2134； 注意看前面1、2交换后，此时1指向3；当3，4交换完之后，链表就是2-1>3->NULL！ 这是题目的第一个trick，解决方案有两种： 1、从倒数开始交换； 2、新增last指针，在每次交换后记录后一个节点，在下一次交换时修改值；比如说在1，2交换后last=1；在交换3，4后，让last->next=4即可；
方案2实现较为简单，增加一个临时变量即可。
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode *ret = head;
if (head && head->next) { // null trick
ret = head->next;
}
ListNode *last = NULL;
while (head && head->next) {
ListNode *tmp = head->next;
head->next = tmp->next;
tmp->next = head;
// update last
if (last && last->next) { // null trick
last->next = tmp;
}
last = head;
head = head->next;
}
return ret;
}
};4.旋转链表
题目链接 题目大意： 给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。
示例 1: 输入: 1->2->3->4->5->NULL, k = 2 输出: 4->5->1->2->3->NULL 解释: 向右旋转 1 步: 5->1->2->3->4->NULL 向右旋转 2 步: 4->5->1->2->3->NULL
示例 2: 输入: 0->1->2->NULL, k = 4 输出: 2->0->1->NULL 解释: 向右旋转 1 步: 2->0->1->NULL 向右旋转 2 步: 1->2->0->NULL 向右旋转 3 步: 0->1->2->NULL 向右旋转 4 步: 2->0->1->NULL
题目解析： 右移k步，假设链表有sum个节点； 先对k处理，k=k%sum，保证k<sum，然后 找到从左到右第k-1个节点p和第k个节点ans，使得p->next=NULL; 然后找到最后一个节点，使得其next等于head； 最后返回ans就好。
复杂度解析： 时间复杂度是O(N) 空间复杂度是O(N)
class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
int sum = 0;
ListNode *p = head;
while (p) {
p = p->next;
++sum;
}
if (sum) {
k = k % sum;
if (k) { // 保险起见
k = sum - k; // 从左到右第k个
p = head;
ListNode *last = NULL;
while (k--) {
last = p;
p = p->next;
}
ListNode *ans = p;
while (p && p->next) {
p = p->next;
}
if (last) {
last->next = NULL;
}
if (p) {
p->next = head;
}
head = ans;
}
}
return head;
}
}leetcode;总结
链表的操作要注意边界，非常容易出现越界、next指针没赋值等。 有一个建议是写的时候注意遍历流程，如果需要改动链表节点则记得初始化，适当写一些冗余代码；如果想不清楚可以先画个图，写下伪代码。