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