LeetCode 143 Reorder List(重排序链表)(Linked List)(*)

简介: 版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/52176455 翻译给定一个链表: L0→L1→…→Ln-1→Ln, 将其重排序成: L0→Ln→L1→Ln-1→L2→Ln-2→…你必须不改变节点的值就地解决这个问题。
版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/52176455

翻译

给定一个链表: L0→L1→…→Ln-1→Ln,
将其重排序成: L0→Ln→L1→Ln-1→L2→Ln-2→…

你必须不改变节点的值就地解决这个问题。

例如,给定{1,2,3,4},重排序成{1, 4, 2, 3}。

原文

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}.

分析

这里我用了3个步骤:

1,找出中间的节点(p1)

1 2 3 4 5  此时中间节点为3
1 2 3 4 5 6 此时中间节点仍为3
  ListNode *p1 = head, *p2 = head;                         
  while (p2->next != NULL && p2->next->next != NULL) {
    p1 = p1->next;
    p2 = p2->next->next;
  }

2,对后半部分进行逆序处理

1 2 3 4 5 处理成: 1 2 3 5 4
1 2 3 4 5 6 处理成: 1 2 3 6 5 4
p1->next = reverseList(p1->next);

ListNode* reverseList(ListNode* head) {
  return reverseListIter(head, NULL);
}

ListNode* reverseListIter(ListNode* head, ListNode* newHead) {
  if (head == NULL) return newHead;
  ListNode* nextNode = head->next;
  head->next = newHead;
  return reverseListIter(nextNode, head);
}

关于这一部分可以看这篇:

LeetCode 206 Reverse Linked List(反转链表)(四步将递归改写成迭代)(*)


3,关键是这一部分

1 2 3 5 4 处理成: 1 5 2 4 3
1 2 3 6 5 4 处理成: 1 6 2 5 3 4
  ListNode *m1 = head;
  while (m1->next != NULL && m1->next->next != NULL) {   
    ListNode *t = m1->next;
    m1->next = p1->next;         // line 1
    p1->next = m1->next->next;   // line 2
    m1->next->next = t;          // line 3
    m1 = t;                      // line 4
  }
1(m1) -> 2(t) -> 3(p1) -> 5 -> 4 -> null

(# line 1, line 2) ->

1(m1) -> 5 -> 4 -> null, 3(p1) -> 4 -> null (此时的t是 2 -> 3 -> 4 -> null(# line 3) ->

1(m1) -> 5 -> 2(t) -> 3(p1) -> 4 -> null

(# line 4) -> 

1 -> 5 -> 2(m1) -> 3(p1) -> 4 -> null

(# line1, line 2)

1 -> 5 -> 2(m1) -> 4, 3(t,p1) -> null

(# line 3)

1 -> 5 -> 2(m1) -> 4 -> 3(t, p1) -> null

(# line 4)

1 -> 5 -> 2 -> 4 -> 3(m1, t, p1) -> null

over
关于 1 2 3 6 5 4 的情况大家可以自己试试

代码

这里写图片描述

相关的文章:如何用Emacs编译C++代码

我这代码是在Emacs上写的,Emacs又是在Terminal中的,博客也是在Emacs中写的。

目录
相关文章
|
4月前
|
存储 C++
C++的list-map链表与映射表
```markdown C++ 中的`list`和`map`提供链表和映射表功能。`list`是双向链表,支持头尾插入删除(`push_front/push_back/pop_front/pop_back`),迭代器遍历及任意位置插入删除。`map`是键值对集合,自动按键排序,支持直接通过键来添加、修改和删除元素。两者均能使用范围for循环遍历,`map`的`count`函数用于统计键值出现次数。 ```
|
5月前
|
存储 C++
C++的list-map链表与映射表
这篇教程介绍了C++中`list`链表和`map`映射表的基本使用。`list`链表可通过`push_front()`、`push_back()`、`pop_front()`和`pop_back()`进行元素的添加和删除,使用迭代器遍历并支持在任意位置插入或删除元素。`map`是一个键值对的集合,元素自动按键值排序,可使用下标操作符或`insert()`函数插入元素,通过迭代器遍历并修改键值对,同时提供`count()`方法统计键值出现次数。教程中包含多个示例代码以帮助理解和学习。
|
5月前
|
Java 索引
Java List实战:手把手教你玩转ArrayList和LinkedList
【6月更文挑战第17天】在Java中,ArrayList和LinkedList是List接口的实现,分别基于动态数组和双向链表。ArrayList适合索引访问,提供快速读取,而LinkedList擅长插入和删除操作。通过示例展示了两者的基本用法,如添加、访问、修改和删除元素。根据场景选择合适的实现能优化性能。
51 0
|
5月前
|
Java 开发者 索引
Java List全攻略:从ArrayList到LinkedList,一网打尽!
【6月更文挑战第17天】Java List详解:ArrayList依赖动态数组,擅长随机访问和遍历,适合少次插入删除;LinkedList基于双向链表,插入删除高效,尤其在头尾操作,但随机访问慢。选择取决于应用场景,理解特性以优化代码。探索ArrayList与LinkedList,提升编程效率!
61 0
|
5月前
|
Java 索引
那些年,我们追过的Java List——ArrayList与LinkedList的爱恨情仇
【6月更文挑战第17天】ArrayList与LinkedList,Java List接口的双子星,各有千秋。ArrayList基于数组,随机访问快速,但插入删除慢;LinkedList用链表实现,插入删除高效,但索引访问慢。两者在爱恨情仇中教会我们权衡选择,成为编程旅程中难忘的记忆。 ```
26 0
|
5月前
|
存储 Java C++
Java List大揭秘:ArrayList vs LinkedList,谁才是真正的王者?
【6月更文挑战第17天】ArrayList和LinkedList是Java中实现List接口的两种方式。ArrayList基于动态数组,适合随机访问和遍历,内存紧凑,但插入删除元素特别是在中间时效率低。LinkedList以双向链表实现,擅长任意位置的插入删除,内存管理灵活,迭代高效,但随机访问性能差。选择使用哪种取决于具体应用场景。
38 0
|
5月前
|
C++ 容器
【C++进阶】深入STL之list:高效双向链表的使用技巧
【C++进阶】深入STL之list:高效双向链表的使用技巧
57 0
|
5月前
|
Java
JavaSE——集合框架一(4/7)-List系列集合:LinkedList集合的底层原理、特有方法、队列、栈
JavaSE——集合框架一(4/7)-List系列集合:LinkedList集合的底层原理、特有方法、队列、栈
45 0
|
5月前
|
存储 NoSQL Redis
Redis第四弹,Redis实现list时候做出的优化ziplist(压缩链表,元素少的情况),可更好的节省空间list——(内部编码:quicklist)Object encoding
Redis第四弹,Redis实现list时候做出的优化ziplist(压缩链表,元素少的情况),可更好的节省空间list——(内部编码:quicklist)Object encoding
|
6月前
|
存储 Python
链表(Linked List)详解
链表(Linked List)详解
50 0