##题目
给定一个链表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()底层实现
无重复字符的最长子串
有时候,卧薪尝胆也是一种鸦片