Leetcode 143. Reorder List (Medium) (cpp)
Tag: Linked List
Difficulty: Medium
/* 143. Reorder List (Medium) 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) {} * }; */ class Solution { public: void reorderList(ListNode* head) { if (head == NULL || head -> next == NULL) { return; } ListNode *s = head, *f = head; while (f -> next != NULL && f -> next -> next != NULL) { s = s -> next; f = f -> next -> next; } ListNode *newhead = reverse(s -> next); s -> next = NULL; s = head; while (newhead != NULL) { ListNode *newheadpos = newhead -> next; newhead -> next = s -> next; s -> next = newhead; s = s -> next -> next; newhead = newheadpos; } } private: ListNode* reverse(ListNode* head) { if (head == NULL || head -> next == NULL) { return head; } ListNode *newhead = reverse(head -> next); head -> next -> next = head; head -> next = NULL; return newhead; } };
