解题思想
首先,拿到一个链表头结点now,(可以理解为当前指针所在位置)
然后定义链表翻转后的头结点pre=null;
循环的条件是链表的头结点不为空,如果为空则返回pre=null。
核心思想是,先把当前节点(now)的next用临时变量(next)保存起来,然后当前节点的next(即now.next)指向pre,然后pre指向当前节点,即(pre=now),然后now往下走一步。完成此步奏后,链表的状态变为0的next指向null,1的next执行2.
继续循环,
image
直到最终now==null结束循环,单链表完成逆转
结构定义
public static class Node {
int data;
Node next;
}
public static class LinkList {
Node head;
}
初始化
/**
* 初始化
*
* @return
*/
public static LinkList init() {
LinkList linkList = new LinkList();
linkList.head = new Node();
// 记住头结点
Node h = linkList.head;
for (int i = 0; i < 10; i++) {
linkList.head.data = i;
// 不初始化尾节点
if (i < 9) {
linkList.head.next = new Node();
linkList.head = linkList.head.next;
}
}
linkList.head = h;
return linkList;
}
翻转
public static Node reverse(Node now) {
Node pre = null;
while (now != null) {
Node next = now.next;
now.next = pre;
pre = now;
now = next;
}
return pre;
}
思想总结
定义pre为翻转后的头结点==null,now为当前节点。如果now不为空,开始循环,循环内容为
临时保存下一个节点
Node temp = now.next;
当前节点的next指向pre
now.next=pre;
pre和now都往下走一步
pre=now;
now=next;
开始下一轮循环。
网友评论