LeetCode 328——奇偶链表（JAVA）

给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。

请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。

示例 1:

输入: 1->2->3->4->5->NULL

输出: 1->3->5->2->4->NULL

示例 2:

输入: 2->1->3->5->6->4->7->NULL

输出: 2->3->6->7->1->5->4->NULL

说明:

应当保持奇数节点和偶数节点的相对顺序。
链表的第一个节点视为奇数节点，第二个节点视为偶数节点，以此类推。

直接上代码：

/**

 * Definition for singly-linked list.

 * public class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode(int x) { val = x; }

 * }

 */

class Solution

{

    public ListNode oddEvenList(ListNode head)

    {

        if(head==null)

            return null;

        if(head.next==null||head.next.next==null)

            return head;

        ListNode odd=head;

        ListNode even=head.next;

        ListNode evenhead=even;//此处的evenhead是链表奇偶化之后偶半链的第一个节点，在下买你的while循环中，evenhead一直处于无前驱节点状态

        while(odd.next!=null&&even.next!=null){

            odd.next=odd.next.next;

            even.next=even.next.next;

            odd=odd.next;

            even=even.next;

        }//经过while循环之后，实际上链表已经被切成两半了，一般是奇链表，一半是偶链表，其中保留了两个指针，一个是odd奇链表的最后一个元素，evenhead是偶链表的第一个节点。

        odd.next=evenhead;//将奇偶链表连接起来

        return head;

    }

}

算法思想：

1、根据奇偶数原则，首先将odd指向head，even指向head.next，同时evenhead也指向head.next。

2、接下来，分别以odd开头“删除”偶数链表，以even 开头删除奇数链表。这样一来将整个链表拆分为两个链表。同时保留了三个节点，分别是odd（奇数链表的最后一个节点），even（偶数链表最后一个节点），evenhead（偶数链表第一个节点）。

3、最后只需将奇偶链表连接起来即可。odd.next=evenhead，大功告成！！！

算法分析：

此算法是在原地修改，并没有开辟新的存储空间，因此空间复杂度是O(1);

对于时间复杂度来说，需要迭代整个链表，因此时间复杂度是O(nodes)。

巴特西

LeetCode 328——奇偶链表（JAVA）

最新文章

热门文章