143. Reorder List
题目:
Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…
You must do this in-place without altering the nodes' values.
For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.
解答：
- 主要思路：快慢指针找到中间节点，将后面的链表反转（前插法），合并链表
- 注意细节，链表为没有空头结点的
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
//reorder list
class Solution{
public:
ListNode* findMiddle(ListNode* head)
{
ListNode* slow=head;
ListNode* fast = head->next;
while ( fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
ListNode* reverse_list(ListNode*head)
{
ListNode* pre = head;
ListNode* temp = head->next;
ListNode* cur = temp;
pre->next = NULL;
while (cur)
{
temp = cur->next;
cur->next = pre;
pre = cur;
cur = temp;
}
return pre;
}
void reorderList(ListNode *head) { //void
if (head==NULL||head->next==NULL||head->next->next==NULL)
{
return;
}
//快慢指针找到中间节点，将后面的链表反转（前插法），合并链表
//另：题目要求是就地解决，应该是不能用辅助栈之类的
ListNode* middel = findMiddle(head);
//反转链表
ListNode* last = reverse_list(middel->next);
middel->next = NULL;
ListNode* temp = NULL;
ListNode* cur = head;
while (last) //防止形成环 middel->next = NULL;
{
temp = last->next;
last->next = cur->next;
cur->next = last;
last = temp;
cur = cur->next->next;
}
return;
}
};