2021-07-16-单链表翻转的两种方法（递归和非递归）

2021-07-16-单链表翻转的两种方法（递归和非递归）

单链表翻转

单链表翻转（reverse函数）返回的是头指针。递归最重要的思想是：边界、返回值、递归调用。单链表翻转使用递归，返回值一定是固定不变的。也就是返回值和递归调用之间不存在关系。

递归调用代码：

private ListNode reverse(ListNode head) { if (head==null||head.next==null) return head; ListNode temp =reverse(head.next); head.next.next=head; head.next=null; return temp; }

这里需要理解的是temp的不变性，以及 head.next.next=head;比较妙，有点巧合的意味

非递归调用代码：

private ListNode reverse(ListNode head) { ListNode pre = new ListNode(-1); pre.next=head; while (head!=null){ ListNode temp = head; head=head.next;//这个位置可不能乱放 哈哈 temp.next=pre.next; pre.next=temp; } return pre.next; }

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。