程序员进阶之算法练习（五十）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就好。