##题目

给定一个链表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;}@Overridepublic 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—

更多精彩推荐


  • 算法题:实现最大(小)栈

  • 算法题:切木头

  • 前序、中序、后续遍历二叉树的非递归实现

  • 前序、中序、后序遍历二叉树通用公式

  • 大数相加

  • 曹操哪里跑!–Java语言实现数字华容道游戏

  • 深入理解Arrays.sort()底层实现

  • 无重复字符的最长子串

  • 有时候,卧薪尝胆也是一种鸦片