Reorder List 最典型的linkedlist题目
https://oj.leetcode.com/problems/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}
.
解题思路:
这道题可以化解为三个子问题。第一,将一个链表分解为两半,也就是取出中间一个节点。第二,对后半链表进行倒置。第三,将前半链表和后半倒置后的链表归并。
第一个问题,前面已经处理过很多次了。可以首先next出整个链表的大小,然后在从头往后N/2个节点。也可以用快慢指针,快指针往后两个,慢指针才往后一个。这样,当快指针到达链表最后,慢指针指向的就是整个链表的中间。这里要注意的是,快指针走的方法,要判断两次。还有,这里取得的midNode实际上是前半链表的最后一个节点,而不是后半链表的第一个节点。
第二个问题,在 Reverse Nodes in k-Group 问题中也做过。
第三个问题,每次用两个引用保存下两个节点就可以。
对于链表的操作还是比较综合的,考虑好几个操作,不是太难,但是需要很细致。掌握的原则还是,链表的特点是可以往后取对象,不能往前。所以不能太快。
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public void reorderList(ListNode head) {
if(head == null || head.next == null){
return;
} //实际上后半段链表的头节点为midNode的下一个节点
ListNode midNode = getMidNode(head);
ListNode secondHead = midNode.next;
midNode.next = null;
secondHead = reverseList(secondHead); //firstList: head-midNode-null
//secondList: secondHead-end-null
mergeList(head, secondHead);
} public ListNode getMidNode(ListNode head){
if(head == null || head.next == null){
return head;
}
ListNode fastNode = head;
ListNode slowNode = head;
while(fastNode.next != null){
fastNode = fastNode.next;
if(fastNode.next != null){
fastNode = fastNode.next;
slowNode = slowNode.next;
}
}
return slowNode;
} public ListNode reverseList(ListNode head){
if(head == null || head.next == null){
return head;
} ListNode preNode = head;
ListNode currentNode = head.next;
ListNode nextNode = head.next.next;
preNode.next = null; while(currentNode != null){
currentNode.next = preNode;
preNode = currentNode;
currentNode = nextNode;
//这个要特别注意,极可能nextNode已经null了
if(nextNode != null){
nextNode = nextNode.next;
}
}
return preNode;
} //两个链表归并,1-2,3-4归并为1-3-2-4
public void mergeList(ListNode head, ListNode secondHead){
while(head != null && secondHead != null){
ListNode headNext = head.next;
head.next = secondHead;
ListNode secondHeadNext = secondHead.next;
secondHead.next = headNext;
head = headNext;
secondHead = secondHeadNext;
}
}
}
上面的方法的时间复杂度为O(n)。之前还写了一个方法,思路是,每次都找到当前链表的最后一个节点,插入到前面的某个位置。例如,1-2-3-4-5-6,然后1-6-2-3-4-5,然后1-6-2-5-3-4。所以每个循环内,都要需要另外O(n)的时间去寻找尾节点,时间复杂度就为O(n^2)了,会time limit exceeded。还是提供下代码吧。
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public void reorderList(ListNode head) {
if(head == null || head.next == null || head.next.next == null){
return;
}
ListNode start = head;
ListNode end = head; while(start.next != null && start.next.next != null){
while(end.next.next != null){
end = end.next;
}
end.next.next = start.next;
start.next = end.next;
end.next = null;
start = start.next.next;
end = start;
}
}
}
update 2015/05/20:
二刷。这题包含寻找链表的中间节点、reverse list、merge list三个链表中比较重要的问题。可以说是leetcode里,链表题目中最为综合的一道,比较重要。一遍AC。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public void reorderList(ListNode head) {
if(head == null || head.next == null) {
return;
}
ListNode preMid = getPreMidNode(head);
// 中间节点是preMid.next
ListNode head2 = reverse(preMid.next);
preMid.next = null;
// 将head和head2开头的两个listmerge
while(head != null && head2 != null) {
ListNode next = head2.next;
head2.next = head.next;
head.next = head2;
head = head2.next;
head2 = next;
}
} // 实际上取得的是中间节点的前一个节点,为了方便将其next置为null
public ListNode getPreMidNode(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while(fast.next != null) {
fast = fast.next;
if(fast.next != null) {
fast = fast.next;
slow = slow.next;
}
}
return slow;
} // 将以head开头的list倒置
public ListNode reverse(ListNode head) {
if(head == null || head.next == null) {
return head;
}
ListNode pre = head;
ListNode cur = head.next;
pre.next = null;
while(cur != null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
}
最新文章
- 关于android中调用系统拍照,返回图片是旋转90度
- JVM初学笔记
- php关于金额比较引发的问题(转)
- EasyUI扩展方法
- 一个free的问题
- ubuntu 下 github 使用方法 以及异常修改
- SpringMVC 整合Jackson报错
- SynchronizedMap和ConcurrentHashMap 区别
- centos7 无法启动网络(service network restart)错误解决办法
- 【BZOJ2160】拉拉队排练(回文树)
- 计算机的Cache和Memory访问时Write-back,Write-through及write allocate的区别
- 鸟哥Linux私房菜基础学习篇学习笔记3
- (摘)linux下yum安装redis以及使用
- chartControl ViewType.Bar 用法测试
- jquery全国省市区三级联动插件distpicker
- Spring Data Redis示例
- Educational Codeforces Round 3 C. Load Balancing
- Codeforces Round #530 (Div. 2) F - Cookies
- vue 笔记二
- Css-常用css