单向链表反转

预防面试被问,做个笔记

需求:

原链表中的数据为:1->2->3->4

反转链表后的数据为:4->3->2->1

反转链表Api

1
public void reverse()//对整个链表进行反转
1
public Node reverse(Node curr)//反转链表的某个结点,并把反转后的结点返回

使用递归可以完成反转,递归反转其实就是从原链表的第一个存数据的结点开始,依次递归调用反转每一个结点, 直到把最后一个结点反转完毕,整个链表就反转完毕。

image-20210506211947433

  1. 调用reverser(Node curr)方法反转每一个结点,从元素1开始;
  2. 如果发现curr还有下一个结点,则递归调用reverser(curr.next)对下一个结点进行反转
  3. 最终递归的出口为元素4结点,因为它没有下一个结点,当到了出口处,让head指向元素4结点,共调用4次
  4. 递归开始返回

image-20210506212712547

如果不理解过程:debug 跟着流程走一遍

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* 反转某个结点
* @param curr 需要反转的结点
* @return 返回反转的结点
*/
public Node reverse(Node curr){
//递归的出口
if (curr.next == null){
head.next = curr;
return curr;
}
//反转结点的下一个结点如果不为空,递归调用反转下一个结点
//如果是head,1,2,3,4 这里进入的为4结点,返回的为head,4
Node prev = reverse(curr.next);
//这里就是反转 head,4,3
prev.next = curr;
curr.next = null;
return curr;
}

评论