首页 > 代码库 > 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，找到链表的中点，断开分为两部分，对链表的后半部分进行反转，然后再合并这两部分链表即可
代码：
1 #include <stddef.h> 2 3 struct ListNode 4 { 5 int val; 6 ListNode *next; 7 ListNode(int x) : val(x), next(NULL) {} 8 }; 9 10 class Solution {11 public:12 void reorderList(ListNode *head) {13 if (!head || !head->next)14 {15 return;16 }17 18 int length = 0;19 ListNode *current = head;20 21 while (current)22 {23 current = current->next;24 ++length;25 }26 27 ListNode *firstHead = head;28 int firstLength = length / 2 + length % 2;29 ListNode *secondHead = NULL;30 current = firstHead;31 32 for (int i = 0; i < firstLength; ++i)33 {34 current = current->next;35 }36 secondHead = current;37 38 //对second链表进行反转39 ListNode dummy(-1);40 dummy.next = secondHead;41 ListNode *pre = secondHead;42 current = secondHead->next;43 44 while (current)45 {46 pre->next = current->next;47 current->next = dummy.next;48 dummy.next = current;49 current = pre->next;50 }51 52 //合并first链表和second链表53 ListNode *firstCur = firstHead;54 ListNode *secondCur = dummy.next;55 ListNode *temp = NULL;56 57 while (firstCur && secondCur)58 {59 temp = secondCur->next;60 secondCur->next = firstCur->next;61 firstCur->next = secondCur;62 63 firstCur = secondCur->next;64 secondCur = temp;65 }66 67 if (firstCur)68 {69 firstCur->next = NULL;70 }71 }72 };
leetcode - Reorder List
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。