LeetCode：206. 反转链表

wenshi11019 发布于2019-08-23 12:08 / 1210人阅读

摘要：示例输入输出进阶你可以迭代或递归地反转链表。可以设置一个指针，指向，保证后续的操作然后将，往前挪动，当然还有，直到为空，这时指向反转后链表的头结点。接下来考虑递归结束的条件非常显然，子链表只有一个节点是递归结束，直接返回该节点。

本文来自 SoulOH 的CSDN 博客，原文地址请点击：https://blog.csdn.net/SoulOH/...
题目:
反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

解答：

迭代方式：

首先判断链表是不是空的，如果是空的，直接返回null；

对于链表：

放两个指针p1, p2:

不能直接将p2 -> next指向p1，否则链表会断掉。

可以设置一个tmp指针，指向 p2 -> next，保证后续的操作：

然后将p1，p2往前挪动，当然还有tmp，直到p2为空，这时p1指向反转后链表的头结点。

最后一次：

刚好结束的时候：

完成了？

不。好像有一点不对劲儿，还多了一个1 -> 2的指针，少了一个null（1 -> null）。正巧head还在，通过head -> next访问多余的指针，指向null（其实一开始就可以这么干的。）

实现代码：

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    //迭代
    if (head == null || head.next == null) return head;
    var p1 = head;
    var p2 = head.next;
    p1.next = null;
    while (p2 !== null) {
        var temp = p2.next;
        p2.next = p1;
        p1 = p2;
        p2 = temp;
    }
    return p1;
};

递归方式：

我们可以从另一个角度考虑这件事：

同样地，对于这样一个链表：

我们要反转它，其实可以

然后我们当作这个子链表已经反转完成：

而我们需要的是：

于是我们可以将上上张图的head.next.next = head：像是这样：

然而仅仅这样是不够的，链表到现在有一个明显的环，我们要把这个环去掉：

令head.next = null即可。

完成。

接下来考虑递归结束的条件：非常显然，子链表只有一个节点是递归结束，直接返回该节点。

当然，这个可以和一开始的空值处理（空链表的处理）写到一起。

下面是具体实现：

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    //递归
    if (head == null || head.next == null) return head;
    var res = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return res;
    
};

本文来自 SoulOH 的CSDN 博客，原文地址请点击：https://blog.csdn.net/SoulOH/...

GPU云服务器云服务器 python反转链表服务器206 LeetCode LeetCode_String

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/97989.html

LeetCode 之 JavaScript 解答第206题 —— 反转链表（Reverse Link

摘要：算法思路两种方法一般反转递归法一般解决定义三个指针，分别为，存储当前结点，指向反转好的结点的头结点，存储下一结点信息。递归法重点分析先确定终止条件当下一结点为时，返回当前节点判断当前的链表是否为递归找到尾结点，将其存储为头结点。 Time：2019/4/23Title: Reverse Linked ListDifficulty: EasyAuthor: 小鹿题目：Reverse...

zhangfaliang 2019-08-23 17:12 评论0 收藏0
LeetCode 206：反转链表 Reverse Linked List

摘要：反转一个单链表。示例输入输出进阶你可以迭代或递归地反转链表。你能否用两种方法解决这道题解题思路每次遍历到最后一位取节点这种方法就算了时间复杂度太高。从链表末尾向头部逐个分离节点，并将节点添加到新链表的末尾。与迭代法原理相似。反转一个单链表。 Reverse a singly linked list. 示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2...

Gilbertat 2019-08-16 18:39 评论0 收藏0
LeetCode 206：反转链表 Reverse Linked List

摘要：反转一个单链表。示例输入输出进阶你可以迭代或递归地反转链表。你能否用两种方法解决这道题解题思路每次遍历到最后一位取节点这种方法就算了时间复杂度太高。从链表末尾向头部逐个分离节点，并将节点添加到新链表的末尾。与迭代法原理相似。反转一个单链表。 Reverse a singly linked list. 示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2...

heartFollower 2019-07-31 11:29 评论0 收藏0
LeetCode 61：旋转链表 Rotate List

摘要：给定一个链表，旋转链表，将链表每个节点向右移动个位置，其中是非负数。按上述思路解，与旋转数组那道题大同小异，来介绍另一种很简单高效的方法。只需在第个节点之后切断，首尾连接即可。另外可能大于链表长度，应当做求余运算。给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。 Given a linked list, rotate the list to the ...

Hwg 2019-07-31 11:30 评论0 收藏0