一、题目描述
给定一个单链表 L 的头节点 head ,单链表 L 表示为:
L0 → L1 → … → Ln – 1 → Ln
请将其重新排列后变为:
L0 → Ln → L1 → Ln – 1 → L2 → Ln – 2 → …
不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
示例 1:
输入:head = [1,2,3,4] 输出:[1,4,2,3]
示例 2:
输入:head = [1,2,3,4,5]
输出:[1,5,2,4,3]
提示:
链表的长度范围为 [1, 5 * 104]
1 <= node.val <= 1000
二、思路讲解及代码实现
1、使用线性表
我们知道,线性表是可以按照下标直接取数据的。我们可以把链表的节点依次存入线性表中,再重新拼接即可。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public void reorderList(ListNode head) {
List<ListNode> list = new ArrayList<>();
ListNode p = head;
while(p!=null){ //将链表放入list中
list.add(p);
p = p.next;
}
int i = 0;
int j = list.size()-1;
ListNode q = new ListNode(0);
while(i<j){
list.get(i).next = list.get(j);
i++;
if(i == j){ //链表长度为奇数或偶数的情况要分开处理
break;
}
list.get(j).next = list.get(i);
j--;
}
//防止成环
list.get(i).next = null;
}
}
时间复杂度: O(N)
空间复杂度: O(N)
二、直接在原链表上修改
找到链表中点,将后半部分翻转,再拼接回原链表
class Solution {
public void reorderList(ListNode head) {
if (head == null) {
return;
}
ListNode mid = middleNode(head);
ListNode l1 = head;
ListNode l2 = mid.next;
//把前半部分和后半部分链表断开
mid.next = null;
l2 = reverseList(l2);
mergeList(l1, l2);
}
public ListNode middleNode(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
public void mergeList(ListNode l1, ListNode l2) {
ListNode l1_tmp;
ListNode l2_tmp;
while (l1 != null && l2 != null) {
l1_tmp = l1.next;
l2_tmp = l2.next;
l1.next = l2;
l1 = l1_tmp;
l2.next = l1;
l2 = l2_tmp;
}
}
}
时间复杂度: O(N)
空间复杂度: O(1)
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
文章由极客之音整理,本文链接:https://www.bmabk.com/index.php/post/125006.html