必会算法：反转链表Ⅰ
##题目
给定一个链表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—
更多精彩推荐