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中写的。

目录
相关文章
|
23天前
【力扣】-- 移除链表元素
【力扣】-- 移除链表元素
31 1
|
30天前
Leetcode第21题(合并两个有序链表)
这篇文章介绍了如何使用非递归和递归方法解决LeetCode第21题,即合并两个有序链表的问题。
47 0
Leetcode第21题(合并两个有序链表)
|
30天前
LeetCode第二十四题(两两交换链表中的节点)
这篇文章介绍了LeetCode第24题的解法,即如何通过使用三个指针(preNode, curNode, curNextNode)来两两交换链表中的节点,并提供了详细的代码实现。
16 0
LeetCode第二十四题(两两交换链表中的节点)
|
30天前
Leetcode第十九题(删除链表的倒数第N个节点)
LeetCode第19题要求删除链表的倒数第N个节点,可以通过快慢指针法在一次遍历中实现。
38 0
Leetcode第十九题(删除链表的倒数第N个节点)
|
30天前
|
索引
力扣(LeetCode)数据结构练习题(3)------链表
力扣(LeetCode)数据结构练习题(3)------链表
72 0
|
30天前
【LeetCode 10】142. 环形链表 II
【LeetCode 10】142. 环形链表 II
20 0
|
30天前
【LeetCode 09】19 删除链表的倒数第 N 个结点
【LeetCode 09】19 删除链表的倒数第 N 个结点
14 0
|
30天前
【LeetCode 08】206 反转链表
【LeetCode 08】206 反转链表
12 0
|
30天前
【LeetCode 06】203.移除链表元素
【LeetCode 06】203.移除链表元素
28 0
|
3月前
|
算法
LeetCode第24题两两交换链表中的节点
这篇文章介绍了LeetCode第24题"两两交换链表中的节点"的解题方法,通过使用虚拟节点和前驱节点技巧,实现了链表中相邻节点的交换。
LeetCode第24题两两交换链表中的节点