首页 > 代码库 > 143. Reorder List
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}.
1 /** 2 * Definition for singly-linked list. 3 * struct ListNode { 4 * int val; 5 * ListNode *next; 6 * ListNode(int x) : val(x), next(NULL) {} 7 * }; 8 */ 9 class Solution {10 public:11 void reorderList(ListNode* head) {12 if(head == NULL || head->next == NULL){13 return;14 }15 16 17 18 ListNode* fast = head;19 ListNode* slow = head;20 21 while(fast->next != NULL && fast->next->next != NULL){22 fast = fast->next->next;23 slow = slow->next;24 }25 fast = slow->next;26 slow->next = NULL;27 28 fast = ReverseList(fast);29 30 slow = head;31 32 while(slow){33 if(fast != NULL){34 ListNode* n = slow->next;35 slow->next = fast;36 ListNode* nn = fast->next;37 fast->next = n;38 fast = nn;39 slow = n;40 }else{41 break;42 }43 }44 }45 46 47 ListNode* ReverseList(ListNode* pHead){48 ListNode* pReversedHead = NULL;49 ListNode* pNode = pHead;50 ListNode* pPrev = NULL;51 52 while(pNode != NULL){53 ListNode* pNext = pNode->next;54 55 if(pNext == NULL){56 pReversedHead = pNode;57 }58 59 pNode->next = pPrev;60 pPrev = pNode;61 pNode = pNext;62 }63 return pReversedHead;64 }65 };
143. Reorder List
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。