算法

每日leetcode-143

143. Reorder List

https://leetcode.com/problems/reorder-list

最简单的算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode* head) {
        if (!head || !(head->next)) {
            return;
        }
        ListNode *last = head->next, *last_pre = head;
        if (!last->next) {
            return;
        }
        while (last->next) {
            last_pre = last;
            last = last->next;
        }
        last->next = head->next;
        head->next = last;
        last_pre->next = NULL;
        reorderList(last->next);
    }
};

写的时候忘了：

  1. !(head->next)判断的时候要先判断head
  2. 在last->next为空的时候如果不return会循环链表

但是复杂度很高，直接递归找最后一个元素

优秀解法：

使用快慢指针直接操作，划分成两部分然后转置后半部分，插入