Revisit: Palindrom LinkedList

Leave a comment

November 6, 2016 by oneOokay

很容易想到的方法就是分三步:

  1. fast & slow pointer find middle
  2. reverse second part
  3. loop

要注意的就是:找到中点之后:当总node为偶数的时候,slow会停在前一段的最后一个;当总node为基数的时候,slow会停在正中间。接下来reverse的转接点比较妙,要注意下。

  • middle.next = reverse(middle.next);
    ListNode p2 = middle.next;

另一个时间O(n) 空间为O(1) 的follow up:人对于reverse linkedlist空间是O(n)还是没有吵起来了。就稍微看一下reverse linkedlist的解法把。

时间O(n)意味着只能loop一遍linkedlist,所以要在找中点的时候同时进行reverse的操作。这里只能够reverse前半段,因为后半段是跳着走的.

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: