博客

奇偶链表

题目描述

• 给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
• 请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。

题解(java)

public class Solution {
    public ListNode oddEvenList(ListNode head) {
        //如果链表头结点为null,则该链表为空链表
        //返回null或head都可
        if (head == null) return head;
        //分别定义两个奇偶链表的头结点
        ListNode odd = head, even = head.next, evenHead = even;
        while (odd.next != null && even.next != null) {
            odd.next = even.next;
            odd = odd.next;
            even.next = odd.next;
            even = even.next;
        }
        //把偶链表的头结点连接到奇链表的尾部
        odd.next = evenHead;
        //最后返回新的链表
        return head;
    }
}

图示

详解

• 简单来说该题就是将原链表先分为两个奇偶链表，最后再将偶链表的头部连接到奇链表的尾部。
• 1>.解题前先判断该链表是否为空链表
• 2>.开始遍历【将偶节点的下一个节点连接奇节点后 odd 指针顺移,将奇节点的下一个指针连接到偶节点后 even 指针顺移】当odd 或 even的下一个节点为空时，遍历结束。
• 3>.遍历结束后将偶链表的头结点（evenHead）连接到奇链表尾部(odd.next)
• 4>.最后返回新链表的头结点 head.

Tips

• 注意：这里默认 head 为奇链表的头结点，需定义一个偶链表的头结点 evenHead(head.next).
• 建议画图理解

声明

• 原作者：E.L.E
• < 本文章著作权归作者所有，商业转载请获得原作者允许，非商业转载请注明来处，欢迎大家评论>