首页 > 代码库 > 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}
.
其实题目的意思就是一个链表分成前后两节,以L0->L1->L2->L3->L4->L5为例,分成L0->L1->L2 以及 L3->L4->L5,然后把后面的部分倒转变成L5->L4->L3, 接着挨个插入到前一个链表中,就OK了。 思路就是这么简单,接下来看一下实现,函数Reverse是实现一个链表的反转,需要注意一下循环结束条件,以及反转时先后顺序;然后reoreder函数里,用fast、slow两个指针来找到链表的中点,从中点割开,成为两个链表。这里说一下,如果节点个数为奇数,那么结束时slow指向的刚好为中点,如果为偶数,是指向将链表均分两部分后,第一部分的尾节点,无论哪种情况,将slow->next作为后一个链表的开始都是正确的。具体实现如下:
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode *Reverse(ListNode *head){ if (head == NULL){ return head; } ListNode *pre_pos = NULL; ListNode *pos = head; ListNode *next_pos = head->next; while(next_pos != NULL){ //注意这里是next_pos pos->next = pre_pos; pre_pos = pos; pos = next_pos; next_pos = next_pos->next; } pos->next = pre_pos; return pos; } void reorderList(ListNode *head) { if (head == NULL) return; ListNode *fast, *slow, *before, *after; fast = slow = before = head; while(fast->next != NULL && fast->next->next != NULL){ slow = slow->next; fast = fast->next->next; } after = Reverse(slow->next); slow->next = NULL; ListNode *insert; while(after != NULL){ insert = after; after = after->next; insert->next = before->next; before->next = insert; before = insert->next; } return; } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。