反转单链表的遍历实现思路比较清晰,基本一看就懂
1>2>3>4>5
1------2>3>4>5
1>2------3>4>5
public Node reverseNode(Node head) {
Node orignHead = head; // 原始链表
Node nowHead = null; // 反转后的链表
while (orignHead.next != null) {
Node temp = orignHead.next;
orignHead.next = nowHead;
nowHead = orignHead;
orignHead = temp;
}
return nowHead;
}
但是递归实现就有些困难了,先写出递归实现的代码
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null)
return head;
ListNode next = head.next;
ListNode new_head = reverseList(next);
next.next = head;
head.next = null;
return new_head;
}
大体思路是
递:
1>2>3>4>5
2>3>4>5
3>4>5
4>5
5
归:
5
5>4
5>4>3
5>4>3>2
5>4>3>2>1
思路大概清楚,还是很难写出上述代码 ,递归方法通过函数调用自身将问题转化为本质相同但规模较小的子问题,是分治策略的具体体现。
ListNode new_head = reverseList(next);
这一段代码把求1>2>3>4>5的反转链表进一步缩小为求2>3>4>5的反转链表,然后继续缩小知道达到某个条件开始回归。
到这里可能还是会有问题,怎么根据问题编写出递归代码来呢?
1.写递归公式最重要的一点就是找到该问题和子问题的关系
2.找到回归条件
带着这两个步骤看下单链表的反转
1.递推公式
:f(n)的反转 = f(n-1)的反转链表指向f(n)的头部Node
2.回归条件
:f(n) n =1就不需要反转了
带着两个步骤去写伪代码
先看下递归公式 head 代表 待反转的链表头部
1.f(n-1) 链表的头部= head.next;
2.f(n-1)的反转链表的头部 = reverese(f(n-1));
3.f(n-1) 反转链表的最后一个元素(3指向的)指向head
4.head.next = null;
return f(n-1)的反转链表头部Node
再看下回归条件
if(head.next==null || head==null){
return head;
}
网友评论