LeetCode 143. 重排链表 JAVA

由King Wang

1 月 3, 2022 code

给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1:
给定链表 1->2->3->4, 重新排列为 1->4->2->3.
示例 2:
给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reorder-list
着作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：
1、利用线性表存储各个节点
2、常规的交换节点
3、也是注意点，要将最后一个结点的next指针置为null，防止死循环

/**
* 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) {

if(head==null||head.next==null) return;
List<ListNode> list=new ArrayList<>();
while(head!=null) {

list.add(head);
head=head.next;
}
int i=0;
int j=list.size()-1;
while(i<j){

list.get(i).next=list.get(j);
i++;
if(i!=j)
list.get(j).next=list.get(i);
j--;
}
list.get(i).next=null;
}
}