逆序"/>
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);}
};
更多推荐
LeetCode 的 C++ 实现(五)链表逆序
发布评论