Reverse LinkedList

Leave a comment

November 2, 2016 by oneOokay

Reverse a singly linked list.


重点是用recursive的方法解吧。

首先Iterative比较简单,注意只需要一个ListNode pre就够了,不需要dummy和next。

public ListNode reverseList(ListNode head) {
//能够处理head == null和head.next==null
ListNode pre = null;
while (head != null) {
ListNode next = head.next;
head.next = pre;
pre = head;
head = next;
}
return pre;
}

Recursive:

什么样的recursive method?因为是reverse,涉及到两个node,所以recursive method里面应该传入两个node,前node和后node。

ListNode reverseNode(current, previous):

  1. if (current == null) return;
  2. 记录下next node(和iterative相似)
  3. 把当前current指向previous
  4. return reverseNode(next, current),进行recursion,处理current和next node.

这个recursion函数的特别之处在于它的返回:

recu1:处理完当前两个node的关系之后,返回下一个recursion的值:recursion进入recur2,开始处理下面一个node的关系;recu1返回值为recur2的返回值;以此类推,recursion的返回值为最后一个recursion的返回值,也就是list末端的那个值。

    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        return reverseNode(head, null);
    }
    
    private ListNode reverseNode(ListNode head, ListNode pre) {
        if (head == null) { //注意这里是return。 recursive一定要一个结束的recursive的return
            return pre;
        }
        ListNode next = head.next;
        head.next = pre;
        return reverseNode(next, head);
    }
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: