526互联

LCR 026. 重排链表

发布时间 2023-08-18 20:37:13作者: Chenyi_li

LCR 026. 重排链表

/**
 * 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> cache = new ArrayList<>();
        while(head!=null){
            cache.add(head);
            head = head.next;
        }

        int l=0;
        int r = cache.size()-1;

        // 需要找到中点位置断开，所以需要分奇偶
        if(cache.size()%2==0){
            cache.get((l+r)/2+1).next = null;
        }else{
            cache.get((l+r)/2).next = null;
        }

        // 修改左右指针所指节点的指向
        while(l+1<r){
            cache.get(l).next = cache.get(r);
            cache.get(r).next = cache.get(l+1);
            l++;
            r--;
        }
    }
}

学习:https://www.bilibili.com/video/BV1Bu411G7uJ/?spm_id_from=333.337.search-card.all.click&vd_source=46d50b5d646b50dcb2a208d3946b1598