3

如何翻转一个链表

 2 years ago
source link: https://hsingko.github.io/tech/datastruct/linkedlist/how-to-reverse-linked-list/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

问题描述#

我们有一个链表，如下：

list.svg

要求是将这个链表从头到尾翻转过来，变成如下形式：

reversed-list.svg

要如何才能做到呢？

解法#

1. 通过栈实现#

前面的节点变成最后的，最后的节点变成最先的，这不就是栈吗？

代码实现也非常简单：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverse(head):
    if head is None:
        return
    stack = []
    while head:
        stack.append(head)
        head = head.next
    tail = new_head = stack.pop()
    while stack:
        tail.next = stack.pop()
        tail = tail.next
    tail.next = None # IMPORTANT prevent cycle
    return new_head

2. “砍头嫁接法”#

用栈实现的缺点是会浪费 O(n) 的空间，事实上让我们重新考虑一下这个问题，翻转的本质是什么呢？

将问题规模缩小到最简有助于我们思考，当只有两个节点时：

two-nodes.svg

第一步，我们需要将节点1 的后继置空：

two-nodes2.svg

第二步，我们将后面的节点的后继改为节点1:

two-nodes3.svg

或许会有人直觉地想到使用双指针法，但是那需要维护各种临时状态，等到下次解决同样的问题又很容易出错。不如让我们转换视角，重新观察上面两幅图……这像不像是从右侧的链表中逐步砍头，然后嫁接到左侧的链表中？这就像是在一条铁轨上，有两条行驶方向相反的两列火车，现在需要将右边的火车车厢全部挂载到左边的火车上，我们可以将右边那辆车的最后一节车厢卸载，然后挂载到另一两车上。

就像是这样：

4-nodes.svg4-nodes1.svg4-nodes2.svg

从代码实现角度看，我们只需要三个变量， head1, head2, cut.

  • head1, 保存左侧链表头
  • head2, 保存右侧链表头
  • cut, 保存砍下来的右侧表头
def reverse(head):
    head1 = None
    head2 = head
    while head2:
        cut = head2
        head2 = head2.next
        cut.next = head1
        head1 = cut
    return head1

扩展问题#

将链表任意部分翻转#

给定一个链表，两个参数 left, right, 两个参数分别代表所需翻转的链表部分的头尾。

参考 leetcode092: https://leetcode.com/problems/reverse-linked-list-ii/

图示： screenshot-05.png

这个问题看似复杂，但只要将其进行分割，我们就会发现这其实很简单。

第一步，我们需要将需要翻转的链表部分切割下来，这涉及到寻找链表的第 n 个节点，简单，只需要一个循环就行了：

def find_nth_node(head, n):
    if n == 0:
        return None
    for i in range(1, n):
        head = head.next
    return head

def cut_left_to_right(head, left, right):
    node_before_left = find_nth_node(head, left-1)
    if node_before_left is None:
        node_at_left = head
    else:
        node_at_left = node_before_left.next
    node_at_right = find_nth_node(head, right)
    node_after_right = node_at_right.next
    node_at_right.next = None
    #todo

实现部分有些细节需要考虑，比如你需要保存切割部分附近的两个节点，以及将尾节点后继置空。

第二步，我们翻转切割下来的链表。我们仍然可以使用之前已经编写过的代码，但是需要做一点小小的改动，额外返回翻转后链表的尾巴，很简单，我们只需要包装一下：

def reverse_ex(head):
    new_tail = head
    new_head = reverse(head)
    return new_head, new_tail

def reverse(head):
    head1 = None
    head2 = head
    while head2:
        cut = head2
        head2 = head2.next
        cut.next = head1
        head1 = cut
    return head1

剩下的就很简单，只需要将翻转后的链表在拼接到原来的链表上就可以了。

def reverse_from_left_to_right(head, left, right):
    node_before_left = find_nth_node(head, left-1)
    if node_before_left is None:
        node_at_left = head
    else:
        node_at_left = node_before_left.next
    node_at_right = find_nth_node(head, right)
    node_after_right = node_at_right.next
    node_at_right.next = None

    sub_head, sub_tail = reverse_ex(node_at_left)
    if node_before_left is None:
        head = sub_head
    else:
        node_before_left.next = sub_head
    if node_after_right:
        sub_tail.next = node_after_right
    return head

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK