LeetCode 的 C++ 实现（五）链表逆序

逆序"/>

LeetCode 的 C++ 实现（五）链表逆序

题目

将给定的单链表L： L 0→L 1→…→L n-1→L n,
重新排序为： L 0→L n →L 1→L n-1→L 2→L n-2→…
要求使用原地算法，并且不改变节点的值
例如：
对于给定的单链表{1,2,3,4}，将其重新排序为{1,4,2,3}.
Given a singly linked list L: L 0→L 1→…→L n-1→L n,
reorder it to: L 0→L n →L 1→L n-1→L 2→L n-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}.

解题思路

1、用快慢指针找到链表的中间节点
2、后半部分逆序123 转为321
3、把逆序完的后半部分和前半部分归并

代码

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode* FindMiddle(ListNode* head){ListNode* fast = head;ListNode* slow = head;while(fast != NULL&&fast->next!= NULL){fast = fast->next->next;slow = slow->next;}return slow;}ListNode* Reverse(ListNode* head){if(head == NULL||head->next == NULL)return head;ListNode* pre = NULL;while(head!=NULL){ListNode* temp = head->next;head->next = pre;pre = head;head = temp;}return pre;}void Merge(ListNode* Head1 , ListNode* Head2){while(Head1 != NULL&&Head2 != NULL){ListNode* TempHead1 = Head1->next;ListNode* TempHead2 = Head2->next;Head1->next = Head2;Head1 = TempHead1;Head2->next = Head1;Head2 = TempHead2;}}void reorderList(ListNode *head) {if(head == NULL || head->next == NULL|| head->next->next == NULL)return;ListNode* middle = FindMiddle(head);ListNode* Temp = middle->next;middle->next = NULL;ListNode* LastHead = Reverse(Temp);Merge(head , LastHead);}
};