143. 重排链表

题目描述

原题
给定一个单链表 LL0→L1→…→L**n-1→Ln , 将其重新排列后变为: L0→L**nL1→L**n-1→L2→L**n-2→…
你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
示例 1:
1
给定链表 1->2->3->4, 重新排列为 1->4->2->3.
Copied!
示例 2:
1
给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.
Copied!

题解

1
/**
2
* Definition for singly-linked list.
3
* public class ListNode {
4
* int val;
5
* ListNode next;
6
* ListNode() {}
7
* ListNode(int val) { this.val = val; }
8
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9
* }
10
*/
11
class Solution {
12
public void reorderList(ListNode head) {
13
if(head==null||head.next==null) return;
14
//1.将所有节点添加到数组中
15
ArrayList<ListNode> list = new ArrayList<>();
16
while(head!=null){
17
list.add(head);
18
head = head.next;
19
}
20
//获取第一个节点
21
head = list.get(0);
22
ListNode node = head;
23
int i = 1;
24
int j = list.size()-1;
25
while(i <= j){
26
node.next = list.get(j);
27
node = node.next;
28
node.next = list.get(i);
29
node = node.next;
30
i++;
31
j--;
32
}
33
node.next = null;
34
}
35
}
Copied!
最近更新 4mo ago
复制链接