【算法面试必刷Java版十四】链表的奇偶重排

盲目刷题，浪费大量时间，博主这里推荐一个面试必刷算法题库，刷完足够面试了。传送门：牛客网面试必刷TOP101

🏄🏻作者简介：CSDN博客专家，华为云云享专家，阿里云专家博主，疯狂coding的普通码农一枚

    

🚴🏻‍♂️个人主页：莫逸风

    

👨🏻‍💻专栏题目地址👉🏻牛客网面试必刷TOP101👈🏻

    

🇨🇳喜欢文章欢迎大家👍🏻点赞🙏🏻关注⭐️收藏📄评论↗️转发

题目：链表的奇偶重排

描述：

给定一个单链表，请设定一个函数，将链表的奇数位节点和偶数位节点分别放在一起，重排后输出。

注意是节点的编号而非节点的数值。

数据范围：节点数量满足 0≤n≤10n5，节点中的值都满足 0≤val≤1000

要求：空间复杂度 O(n)，时间复杂度 O(n)

思路：多指针标记

1. 遍历入参链表 。
2. 使用双指针l1,l2分别连接奇数节点和偶数节点。
3. l1.next = l2。
4. 注意总长度为偶数时，偶数链表最后一个节点的next不为null，所以额外加一步将偶数链表的最后一个节点的next指针置位null。

代码：

public ListNode oddEvenList(ListNode head) {
    // write code here
    ListNode cur = head;
    ListNode l1 = new ListNode(-1);
    ListNode l1Cur = l1;
    ListNode l2 = new ListNode(-1);
    ListNode l2Cur = l2;
    int i = 1;
    while (cur != null) {
        if (i % 2 == 1){
            l1Cur.next = cur;
            l1Cur = l1Cur.next;
        }else {
            l2Cur.next = cur;
            l2Cur = l2Cur.next;
        }
        i++;
        cur =cur.next;
    }
    // 基数l2最后一个节点的next不为null
    l2Cur.next = null;
    l1Cur.next = l2.next;
    return l1.next;
}

推荐牛客网面试必刷算法题库，刷完足够面试了。传送门：牛客网面试必刷TOP101