必会算法：反转链表Ⅰ

##题目

给定一个链表head，要求反转这个链表

链表节点定义如下

package com.dai.common;

public class Node {
    public Integer value;
    public Node next;

    public Node() {
    }

    public Node(Integer value) {
        this.value = value;
    }

    public Node(Integer value, Node next) {
        this.value = value;
        this.next = next;
    }

    @Override
    public String toString() {
        Node temp = this;
        StringBuilder str = new StringBuilder();
        while (temp != null) {
            str.append(temp.value).append("->");
            temp = temp.next;
        }
        str.append("null");
        return str.toString();
    }
}

##解题思路

首先先考虑极端情况

第一种情况

当链表为null或者只有一个节点的时候

不存在反转的情况，直接返回就行

第二种情况

当链表有两个节点的时候

也就是head.next.next=null的时候

也很简单，定义两个pre和cur

分别指向第一个和第二个节点

然后令pre.next指向空，cur.next指向pre

此时，cur就是反转之后的链表了

第三种情况

当链表的节点数为3的时候呢？

可以采用整体法的思路

在第二种情况的基础上，将前两个节点看成一个整体，当作一个节点

此时pre还是指向的“第一个节点”，cur还是指向的第二个节点

那这样问题就简单了，还是采用第二种情况的方式反转链表就行了

依此类推

只需要搞定前两种情况

剩下的情况放到一个循环中做一样的处理就行

##算法图解

如下图是一个拥有八个节点的链表

图片

为了方便理解，我们cur.next也作为一个单独的指针定义出来

此时可以将pre指向第一个节点

cur指向第二个节点

因为第一个节点在反转后是需要指向null的

所以此时pre.next=null

图片

接着判断一下cur是否为null

不为null则需要将cur.next指向pre

因为第二个节点指向第一个节点之后

后续的节点就无法拿到了，所以需要先将next指向第三个节点

图片

然后将cur.next指向pre

图片

然后将pre=cur

图片

令cur=next，指向第三个节点

** 注意观察 ！**

此时如果将pre指向的链表看做一个节点

是不是又回到了最初的状态？

图片

同样的方法进行pre、cur、next指针的变动

只要cur或者next不为null，就可以一直走下去

图片 图片

直到最后，cur或者next为null

链表也反转完成了

pre指向的链表就是反转后的链表啦！

图片

##代码实现

package com.dai.code;

import com.dai.common.Node;

public class ReverseLinkedList1 {

    public static Node reverseLinkedList(Node head) {
        // 当链表为空，或者长度为1的时候走这里
        if (null == head || null == head.next) {
            return head;
        }
        // 当链表只有两个节点的时候
        Node pre = head;
        Node cur = head.next;
        Node next = cur;
        pre.next = null;

        // 当链表有三个及以上节点的时候
        while (next != null) {
            next = next.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }

        return pre;
    }
}

测试一下

public class ReverseLinkedList1 {
    public static void main(String[] args) {
        Node head = new Node(1);
        Node temp = head;
        for (int i = 2; i < 10; i++) {
            temp.next = new Node(i);
            temp = temp.next;
        }
        System.out.println(head + "：：反转：：" + reverseLinkedList(head));
    }
}

图片

文/戴先生@2021年11月19日

---end---

更多精彩推荐