要求in-place，所以不能用stack。解法分三个步骤：
- 分解，分成前半段和后半段两个链表
- 翻转，reverse第二个链表
- 合并，将两个链表merge起来
注意我们用fast.next ！= null && fast.next.next ！= null来判断分解的结束情况，因为这样可以让partition之后的链表前半部分等于后半部分，或者前半部分长度比后半部分少1，从而符合题目的要求。Merge的时候就相当于把第二个链表每隔一个node插入第一个链表当中，总的时间复杂度仍然是O(N)，常数空间。代码如下：
No comments:
Post a Comment