【题目】
Given a singly linked listL: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}
.
【题意】
给定一个单链表L:L0→L1→...→LN-1→LN,
它重新排列到:L0→LN→L1→LN-1→L2→LN-2→...
【分析】
题目规定要 in-place,也就是说只能使用 O(1) 的空间。
可以找到中间节点,断开,把后半截单链表 reverse 一下,再合并两个单链表。
【代码】
/*********************************
* 日期:2014-01-31
* 作者:SJF0115
* 题号: Reorder List
* 来源:http://oj.leetcode.com/problems/reorder-list/
* 结果:AC
* 来源:LeetCode
* 总结:
**********************************/
#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode* reorderList(ListNode *head) {
if(head == NULL || head->next == NULL){
return head;
}
//找中间节点
ListNode *slow = head,*fast = head,*pre = NULL,*pre2 = NULL,*temp = NULL;
while(fast != NULL && fast->next != NULL){
pre = slow;
slow = slow->next;
fast = fast->next->next;
}
//在中间截断成两个单链表
pre->next = NULL;
ListNode *head2 = reverse(slow);
//合并
pre = head;
pre2 = head2;
while(pre->next != NULL){
temp = pre2->next;
//合并
pre2->next = pre->next;
pre->next = pre2;
//下一个元素
pre = pre->next->next;
pre2 = temp;
}
pre->next = pre2;
return head;
}
private:
ListNode* reverse(ListNode *head){
if(head == NULL || head->next == NULL){
return head;
}
ListNode *dummy = (ListNode*)malloc(sizeof(ListNode));
dummy->next = head;
ListNode *tail = head,*cur = head->next;
while(cur != NULL){
//删除cur元素
tail->next = cur->next;
//插入
cur->next = dummy->next;
dummy->next = cur;
cur = tail->next;
}
return dummy->next;
}
};
int main() {
Solution solution;
int A[] = {1,2,3,4,5,6};
ListNode *head = (ListNode*)malloc(sizeof(ListNode));
head->next = NULL;
ListNode *node;
ListNode *pre = head;
for(int i = 0;i < 6;i++){
node = (ListNode*)malloc(sizeof(ListNode));
node->val = A[i];
node->next = NULL;
pre->next = node;
pre = node;
}
head = solution.reorderList(head->next);
while(head != NULL){
printf("%d ",head->val);
head = head->next;
}
//printf("Result:%d\n",result);
return 0;
}
分享到:
相关推荐
这是LeetCode中Linked List所有题目的参考代码。(截止到目前为止:2015年12月14日)。
leetcode-codelist 食用指南(持续更新中...) 文件名说明:leetcode-题号-题目类型 目前更新重点-每日一题 tips:闲暇时间刷刷题,面试之前不用慌。 常见思路整理 前缀和 327 区间和的个数 差分 动态规划 845 最长...
刷LeetCode刷LeetCode刷LeetCode刷LeetCode刷LeetCode
list-leetcode DEPRECATED(不再维护) 相关功能已并入,此仓库不再维护。 简介 输入你的leetcode账号密码,就能立即生成包含题号、标题、链接、难度、总提交数、总通过数、通过率、是否付费和已解决等内容的,所有...
文件中包含了LeetCode中Tag为LinkedList的题目参考代码。
leetcode中文版
vs code LeetCode 插件
大佬的leetcode刷题笔记(c++版本)
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101.zip
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101_源码.zip
leetcode刷题之动态规划
100个leetCode详细解答
LeetCode 刷题汇总1
LeetCode 选讲1
leetcode 2 力码助手 应用程序接口 列表 var List = require ( 'leetcode' ) . List ; 列表节点 ListNode构造函数,用于在列表中创建节点。 ListNode.prototype.toArray 将列表转换为数组。 通常用于调试。 var List...
terminal-leetcode, 终端Leetcode是基于终端的Leetcode网站查看器 终端 leetcode终端leetcode是基于终端的leetcode网站查看器。本项目是由 RTV 激发的。 我最近正在学习本地化的反应,以实践我的新知识,并根据这个...
leetcode刷题, 直接用leetcode的分类方式.
该分类为结合《算法导论》的内容,给出Leetcode题目分类。题目主要集中在Leetcode的前400题中,也包括有后面的一些经典值得刷的题。该题目分类按照算法和数据结构排版,即可供单独Leetcode刷题使用,也可以配合学习...
leetcode Fighting for a job! 记录找工作期间搬运的题,全部使用Java实现,本人C++鶸 1 双指针 编号 题目 LeetCode 11 Container With Most Water LeetCode 19 Remove Nth Node From End of List LeetCode 42 ...
leetcode高频面试笔试题150+道,亲身总结。