3种方法 按照时间复杂度排序
第一种 最简单的，利用vector来存储每一个链表节点的指针，然后利用前后的双指针，把vector中的节点拼接在一起
/*** 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) {vector<ListNode*> v;auto p = head;while(p){v.push_back(p);p = p->next;}ListNode* dummy = new ListNode(0);p = dummy;int l = 0, r = v.size() - 1;while(l <= r){cout << "l: " << l << " r: " << r << endl;p->next = v[l++];p = p->next;if(l <= r){p->next = v[r--];p = p->next;}}p->next = nullptr;}};
第二种 利用递归的方式
从中间开始，每次只处理左右两边新增的
我们来考虑一下，处理了一层之后，外层需要什么呢？
需要返回一个内层头指针，用来拼接
那么这个内层头指针怎么拼接呢？
本层头指针->本层的尾巴->内层头指针
本层的尾巴怎么知道的？
因为每一层都是削去头和尾，所以只要知道这一层的总长度就可以知道尾巴在哪里了
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
ListNode* dfs(ListNode* head, int len)
{
if(len == 0)
return nullptr;
if(len == 1)
{
head->next = nullptr;
return head;
}
auto tail = head;
int cnt = len - 1;
while(cnt--)
{
tail = tail -> next;
}
auto tmp = head->next;
head->next = tail;
tail->next = dfs(tmp, len - 2);
return head;
}
public:
void reorderList(ListNode* head) {
int len = 0;
auto p = head;
while(p)
{
len++;
p = p->next;
}
p = head;
dfs(p, len);
}
};
进一步优化，是否可以不用每次都用循环来算一次尾巴？我的内层递归是否能返回我的尾巴给我？也就是说返回两个东西：一个是内层头指针，一个是本层的尾巴，这样我就不用循环找尾巴了。
class Solution {
pair<ListNode*, ListNode*> dfs(ListNode* head, int len)
{
cout << len << endl;
if(len == 0)
{
return {nullptr, head};
}
if(len == 1)
{
auto tail = head->next;
head->next = nullptr;
return {head, tail};
}
auto tmp = head->next;
auto x = dfs(tmp, len - 2);
//cout << x.first->val << ' ' << x.second->val << endl;
ListNode* tail = x.second;
head->next = tail;
tmp = tail->next;
tail->next = x.first;
return {head, tmp};
}
public:
void reorderList(ListNode* head) {
int len = 0;
auto p = head;
while(p)
{
len++;
p = p->next;
}
p = head;
//cout << len << endl;
dfs(p, len);
}
};
再进一步优化
是否需要返回内层头指针？似乎不是需要的，因为我本层头指针的next就是内层的头指针呀
class Solution {
ListNode* dfs(ListNode* head, int len)
{
//cout << len << endl;
if(len == 2)
{
auto tail = head->next->next;
head->next->next = nullptr;
return tail;
}
if(len == 1)
{
auto tail = head->next;
head->next = nullptr;
return tail;
}
auto tmp = dfs(head->next, len - 2);
auto tail = tmp->next;
tmp->next = head->next;
//cout << x.first->val << ' ' << x.second->val << endl;
head->next = tmp;
return tail;
}
public:
void reorderList(ListNode* head) {
if(!head) return;
int len = 0;
auto p = head;
while(p)
{
len++;
p = p->next;
}
p = head;
//cout << len << endl;
dfs(p, len);
}
};
第三种方法
把链表分成两半，然后把后面的一半反转，然后再把两半的链表拼接在一起
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
ListNode* reverse(ListNode* head)
{
ListNode *cur = head, *prev = nullptr;
while(cur)
{
auto nxt = cur->next;
cur->next = prev;
prev = cur;
cur = nxt;
}
return prev;
}
public:
void reorderList(ListNode* head) {
ListNode* dummy = new ListNode(0);
dummy->next = head;
auto slow = dummy, fast = dummy;
while(fast!= nullptr && fast->next != nullptr)
{
slow = slow->next;
fast = fast->next->next;
}
//奇数是中间，偶数是中间的左边
auto left = head, right = slow->next;//左边的多右边少
slow->next = nullptr;
right = reverse(right);
auto pt = dummy;
while(left || right)
{
if(left)
{
dummy->next = left;
left = left->next;
dummy = dummy->next;
}
if(right)
{
dummy->next = right;
right = right->next;
dummy = dummy->next;
}
}
}
};
第二次写题，vector的方式
/**
* 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) {
ListNode* dummy = new ListNode(-1);
deque<ListNode*> q;
ListNode* tmp = head;
while(tmp)
{
q.push_back(tmp);
tmp = tmp->next;
}
tmp = dummy;
// cout << q.size() << endl;
while(q.size())
{
tmp->next = q.front();
q.pop_front();
tmp = tmp->next;
if(!q.size()) break;
// cout << q.size() << endl;
tmp->next = q.back();
q.pop_back();
tmp = tmp->next;
}
tmp->next = nullptr;
}
};
dfs的做法
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
ListNode* dfs(ListNode* head, int len)
{
if(len == 1)
{
head->next = nullptr;
return head;
}
if(len == 2)
{
head->next->next = nullptr;
return head;
}
ListNode* tail = head;
for(int i = 1; i < len; i++)
tail = tail->next;
tail->next = dfs(head->next, len - 2);
head->next = tail;
return head;
}
public:
void reorderList(ListNode* head) {
if(!head) return;
int len = 0;
ListNode* tmp = head;
while(tmp)
{
len++;
tmp = tmp->next;
}
dfs(head, len);
// return dfs(head, len);
}
};
第三次写题
这道题使用递归是一种很巧妙的做法，巧妙在于dfs返回的是什么东西。如果按照层的想法，我们每次返回的应该是内层的开头指针。像这样：
这道题使用递归是一种很巧妙的做法，巧妙在于dfs返回的是什么东西。如果按照层的想法，我们每次返回的应该是内层的开头指针。像这样：
_
这种方式有没有什么缺陷？ 有的！ 就是每一层都要O(n)来找一下尾部节点！
那么有没有什么改进方式？ 哈，就是下面的方式👇。仔细观察我们这个修改后的排列，其实它每一层返回的都是dfs的head，也就是外面一层的head的next，仔细看其实就是链表的前半段。所以，如果说我们可以让内层帮我们外层找尾巴，时间复杂度就可以下降下来了！
找尾巴的方式也很巧妙，因为啊，这个尾巴其实一直都在链表的后半段，而且这一层尾巴的next是下一层的尾巴！！
这种方式有没有什么缺陷？ 有的！ 就是每一层都要O(n)来找一下尾部节点！
那么有没有什么改进方式？ 哈，就是下面的方式👇。仔细观察我们这个修改后的排列，其实它每一层返回的都是dfs的head，也就是外面一层的head的next，仔细看其实就是链表的前半段。所以，如果说我们可以让内层帮我们外层找尾巴，时间复杂度就可以下降下来了！
找尾巴的方式也很巧妙，因为啊，这个尾巴其实一直都在链表的后半段，而且这一层尾巴的next是下一层的尾巴！！
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
ListNode* dfs(ListNode* head, int iLen)
{
if(iLen <= 2)
{
if(iLen == 1)
{
head->next = nullptr;
return head;
}
else if(iLen == 2)
{
head->next->next = nullptr;
return head;
}
}
ListNode* tail = head;
for(int i = 0; i < iLen - 1; i++)
tail = tail->next;
tail->next = dfs(head->next, iLen - 2);
head->next = tail;
return head;
}
public:
void reorderList(ListNode* head) {
if(!head) return;
int iLen = 0;
ListNode* pt = head;
while(pt)
{
iLen++;
pt = pt->next;
}
dfs(head, iLen);
}
};
第四次写题
递归的做法
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
ListNode* dfs(ListNode* head, int len)
{
if(len == 1)
{
ListNode* tail = head->next;
head->next= nullptr;
return tail;
}
if(len == 2)
{
ListNode* tail = head->next->next;
head->next->next = nullptr;
return tail;
}
ListNode* tmp = dfs(head->next, len - 2);
ListNode* tail = tmp->next;
tmp->next = head->next;
head->next = tmp;
return tail;
}
public:
void reorderList(ListNode* head) {
if(!head) return;
ListNode* pt = head;
int len = 0;
while(pt)
{
len++;
pt = pt->next;
}
dfs(head, len);
}
};
deque的做法
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
void reorderList(ListNode* head) {
if(!head) return;
deque<ListNode*> dq;
ListNode* pt = head;
while(pt)
{
dq.push_back(pt);
pt = pt->next;
}
ListNode* dummy = new ListNode(-1);
pt = dummy;
while(dq.size())
{
pt->next = dq.front();
dq.pop_front();
pt = pt->next;
if(dq.size())
{
pt->next = dq.back();
dq.pop_back();
pt = pt->next;
}
}
pt->next = nullptr;
}
};
若有收获，就点个赞吧
0 人点赞
