运维开发网

【链表问题】如何优雅着反转单链表

运维开发网 https://www.qedev.com 2020-11-27 10:39 出处:51CTO 作者:帅地玩编程
前言以专题的形式更新刷题贴,欢迎跟我一起学习刷题,相信我,你的坚持,绝对会有意想不到的收获。每道题会提供简单的解答,如果你有更优雅的做法,欢迎提供指点,谢谢【题目描述】反转单链表。例如链表为:1->2->3->4反转后为4->3->2->1【要求】如果链表的长度为N,时间复杂度达到O(N),额外空间复杂度达到O(1)【难度】士:★☆☆☆【解答】方法1这道题还是挺

前言

以专题的形式更新刷题贴,欢迎跟我一起学习刷题,相信我,你的坚持,绝对会有意想不到的收获。每道题会提供简单的解答,如果你有更优雅的做法,欢迎提供指点,谢谢

【题目描述】

反转单链表。例如链表为:

1->2->3->4

反转后为

4->3->2->1

【要求】

如果链表的长度为 N, 时间复杂度达到 O(N), 额外空间复杂度达到 O(1)

【难度】

士:★☆☆☆

【解答】

方法1

这道题还是挺简单的,当我们在反转一个节点的时候,把一个节点的后驱改为指向它前驱就可以了。这里需要注意的点就是,当你把当前节点的后驱指向前驱的时候,这个时候链表会被截断,也就是说后面的节点和当前节点分开了,所以我们需要一个变量来保存当前节点的后驱,以访丢失。

具体代码如下:

代码如下

1//节点
2class Node{
3    public int value;
4    public Node next;
5    public Node(int data) {
6        this.value = data;
7    }
8}

主要代码

1//反转单链表

2public static Node reverseList(Node head) {

3 Node next = null;//指向当前节点的后驱

4 Node pre = null;//指向当前节点的前驱

5 while (head != null) {

6 next = head.next;

7 //当前节点的后驱指向前驱

8 head.next = pre;

9 pre = head;

10 //处理下一个节点

11 head = next;

12 }

13 return pre;

方法二

这道题也可以用递归来做,假设 方法 reverse() 的功能是将单链表进行逆转。采用递归的方法时,我们可以不断着对子链表进行递归。例如对于如下的链表:

【链表问题】如何优雅着反转单链表

我们对子链表 2->3->4 进行递归,即

Node newList = reverse(head.next)。递归之后的结果如下:

【链表问题】如何优雅着反转单链表

逆转之后子链表 2->3->变为了 4->3->2。

注意,我刚才假设 reverse() 的功能就是对链表进行逆转。不过此时节点 1 仍然是指向节点 2 的。这个时候,我们再把节点1 和 2逆转一下,然后 1 的下一个节点指向 null 就可以了。如图:

【链表问题】如何优雅着反转单链表

递归的结束条件就是:当子链表只有一个节点,或者为 null 时,递归结束。代码如下:

 1    //用递归的方法反转链表
 2    public static Node reverseList2(Node head){
 3        if (head == null || head.next == null) {
 4            return head;
 5        }
 6        //递归反转子lian链表
 7        Node newList = reverseList2(head.next);
 8        //第三张图
 9        head.next.next = head;
10        head.next = null;
11        return newList;
12    }

问题拓展

题目:反转部分链表节点

【题目描述】

题目:给定一个单向链表的头结点head,以及两个整数from和to ,在单项链表上把第from个节点和第to个节点这一部分进行反转

列如:

1->2->3->4->5->null,from=2,to=4

结果:1->4->3->2->5->null

列如:

1->2->3->null from=1,to=3

结果为3->2->1->null

【要求】

1、如果链表长度为N,时间复杂度要求为O(N),额外空间复杂度要求为O(1)

2、如果不满足1<=from<=to<=N,则不调整

【难度】

士:★☆☆☆

【解答】

可以自己动手做一下或者想一下,如果想要获取答案,可以在公众号回复 解答2 获取代码

  • End -

    往期

【链表问题】删除单链表的中间节点

【链表问题】删除单链表中的第K个节点

【算法实战】生成窗口最大值数组

【链表问题】如何优雅着反转单链表

扫码领视频副本.gif

0

精彩评论

暂无评论...
验证码 换一张
取 消

关注公众号