Leetcode日记–328. Odd Even Liked List

发布于 2020-11-14  117 次阅读


题目如下:

Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.

You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.

Example 1:

Input: 1->2->3->4->5->NULL
Output: 1->3->5->2->4->NULL

Example 2:

Input: 2->1->3->5->6->4->7->NULL
Output: 2->3->6->7->1->5->4->NULL
 

Constraints:

The relative order inside both the even and odd groups should remain as it was in the input.
The first node is considered odd, the second node even and so on …
The length of the linked list is between [0, 10^4].

思路:

本题要求了在奇数数列和偶数数列中的相对位置不变,否则可以直接使用快慢指针,一个指针指向偶数节点,并每次向后移动两个节点位置;另一个指针从第一个节点开始一步一步后移,每次两个指针交换值,这样当前面都是奇数节点时,显然,后面的都是偶数节点。但是显然,这样并不能保证稳定性,也就是相对位置会遭到破坏。

那么我们就使用最直观暴力的做法就是了,一个奇数节点指针,一个偶数节点指针,再来一个指针记录一下第一个偶节点,方便后续合并两个奇偶链表。

代码:

/**
 * 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 ListNode oddEvenList(ListNode head) {
        if(head==null||head.next==null||head.next.next==null)
            return head;
        // ListNode oddHead = head;
        ListNode evenHead = head.next;
        ListNode oddCur = head;
        ListNode evenCur = evenHead;
        while(oddCur!=null&&evenCur!=null){
            oddCur.next = oddCur.next.next;
            if (oddCur.next!=null)
                oddCur = oddCur.next;
            if(evenCur.next==null)
                break;
            else{
                evenCur.next = evenCur.next.next;
                evenCur = evenCur.next;
            }
        }
        oddCur.next = evenHead;
        return head;
    }
}

以上是我的代码,下面是官方的代码,事实上官方的代码更加简洁,更漂亮。

class Solution {
    public ListNode oddEvenList(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode evenHead = head.next;
        ListNode odd = head, even = evenHead;
        while (even != null && even.next != null) {
            odd.next = even.next;
            odd = odd.next;
            even.next = odd.next;
            even = even.next;
        }
        odd.next = evenHead;
        return head;
    }
}

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/odd-even-linked-list/solution/qi-ou-lian-biao-by-leetcode-solution/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

你好哇!欢迎来到雷公马碎碎念的地方:)