反转单向链表的两种写法（迭代、递归）

题目：反转单向链表，单向链表的定义为：

public class ListNode { int val; ListNode next; public ListNode (int val) {this.val = val;} }

原题目：LeetCode--206. Reverse Linked List

Reverse a singly linked list.

Example:

Input: 1->2->3->4->5->NULL Output: 5->4->3->2->1->NULL

Follow up:

A linked list can be reversed either iteratively or recursively. Could you implement both?

先看迭代的写法：

public ListNode reverseList (ListNode head) { if (head == null || head.next == null) { return head; } ListNode prev = null; ListNode next = null; while (head != null) { next = head.next; head.next = prev; prev = head; head = next; } return prev; }

再看递归的写法：

public ListNode reverseList (ListNode head) { if (head == null || head.next == null) { return head; } ListNode node = reverseListRecur(head.next); head.next.next = head; head.next = null; return node; }

参考：Solution

 

好了，我们下期见！！