链表专题 (I)：Leetcode 19 删除链表的倒数第N个节点 + Leetcode 24 两两交换链表中的节点 + Leetcode 61 旋转链表

链表专题 (I)：Leetcode 19 删除链表的倒数第N个节点 + Leetcode 24 两两交换链表中的节点 + Leetcode 61 旋转链表

如何根据列表构建链表在：

Python 面向对象编程自学笔记 + 基本数据结构实现（链表，跳表，二叉树）

这篇文章的数据结构实现部分中。

Leetcode 19 删除链表的倒数第N个节点

题目描述

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
1
2

说明：

给定的 n 保证是有效的。

进阶：

你能尝试使用一趟扫描实现吗？

题解

既然要追求刺激，那么我们贯彻到底：直接满足这个进阶的请求。

我们需要两个节点：==一个从头节点出发；一个从头节点+N个节点的位置进行出发。==那么当第二个节点达到末尾的时候，头节点的下一个节点就是要删除的位置。那么加上删除位置是否为边界点的讨论就可以轻松解决这道题：

边界点一共有这几种情况：

1. 删除的节点是头结点的时候
2. 删除的节点是末尾节点

整个函数是这样的：

class Solution(object):
    def removeNthFromEnd(self, head, n):
        front = head
        second = None
        count = 0
        flag = 0
        while front:
            if front.next:
                front = front.next
                count = count + 1
                if count > n-1:
                    if flag == 0:
                        second = head
                        flag = 1
                    else:
                        second = second.next
            else:
                break
        if second == None:
            res = head.next
            head = None
            return res
        else:
            if second.next:
                temp = second.next.next
                second.next = temp
                temp = None
            else:
                second.next = None
        return head
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

运行结果

运行用时：16 ms

内存消耗： 11.7 MB

Leetcode 24 两两交换链表中的节点

题目描述

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例:

给定 1->2->3->4, 你应该返回 2->1->4->3.
1

题解

没有什么特别的方法，就是从头往后遍历一遍，两两交换一下，如果只有一个节点或之后没有后继节点了，就退出遍历。整个流程如下：

class Solution(object):
    def swapPairs(self, head):
        if not head:
            return head
        cur1 = head
        cur2 = head.next
        if not cur2:
            return head
        while True:
            if cur1 == head:
                cur1.next = cur2.next
                cur2.next = cur1
                head = cur2
            else:
                if not cur1.next:
                    break
                else:
                    if not cur1.next.next:
                        break
                    else:
                        temp1 = cur1.next
                        temp2 = cur1.next.next
                        temp1.next = temp2.next
                        cur1.next = temp2
                        temp2.next = temp1
                        cur1 = temp1
        return head
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

运行结果

Leetcode 61 旋转链表

题目描述

给定一个链表，旋转链表，将链表每个节点向右移动 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
1
2
3
4
5

示例 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
1
2
3
4
5
6
7

题解

实际上，不用那么听话他说挪几次就挪几次，如果能求出整个链表的长度，只需要挪 $k\text{ mod }len(list)$ 就可以了。

首先，先将链表的首尾连接起来，连成一个环（在连接的时候可以求出链的长度），然后从头结点开始，走 $len(list)-(k\text{ mod }len(list))$ 步，这个点就是我们的新头节点，从这里断开，输出这个节点就可以了（因为已经是环链，因此之前的已经连接到了链表尾了）。

代码如下：

class Solution(object):
    def rotateRight(self, head, k):
        if (not head) | (k == 0):
            return head
        elif not head.next:
            return head
        cur = head
        length = 1
        while cur.next:
            cur = cur.next
            length = length + 1
        cur.next = head
        k = k % length
        if k == 0:
            cur.next = None
            return head
        cur = head
        for i in range(1, length - k):
            cur = cur.next
        head = cur.next
        cur.next = None
        return head
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

运行结果

执行时间：24 ms

内存消耗：11.9 MB