“This is the 26th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

1, the title

Given a singly linked list, rank all the odd and even nodes together. Note that the odd and even nodes here refer to the parity of node numbers, not the parity of node values.

Try using the in situ algorithm. The space complexity of your algorithm should be O(1)O(1)O(1) O(1) and the time complexity should be O(Nodes)O(Nodes)O(Nodes), where nodesnodesnodes is the total number of nodes.

Example 1:

Input: 1->2->3->4->5->NULL Output: 1->3->5->2->4->NULLCopy the code

Example 2:

Input: 1 - > 2 - > 3 - > 5 - > 4 - > 7-6 - > > NULL output: 2 - > 3 - > 6-7-1 - > > > 5 - > 4 - > NULLCopy the code

Description:

  • The relative order of odd and even nodes should be maintained.
  • The first node in the list is considered an odd number, the second an even number, and so on.

2, train of thought

(linked list)O(n)O(n) O(n)

According to the parity of node numbering, we can separate odd and even nodes into odd and even linked lists, and then join the even linked lists after the odd linked list, the combined linked list is the result linked list.

The specific process is as follows:

1. Iterate through the list from front to back, maintaining four Pointers: odd list heads, odd list tails, even list heads, and even list tails.

2. After traversal, insert the odd-numbered nodes after the last nodes of the odd-numbered list, and insert the even-numbered nodes after the last nodes of the even-numbered list.

  • P = head->next->next

  • The next pointer to oddTail points to p and moves one bit later, that is, oddTail = oddTail->next = p.

  • The p pointer moves back one bit.

  • The next pointer to evenTail at the end of the even-numbered list points to p and moves one bit later, i.e. EvenTail = evenTail-> Next = P.

  • Move the p pointer back one bit and repeat the process.

Finally, we split the odd-even list, as shown below:

3. After traversing the entire list, insert the even-numbered list head node after the odd-numbered list last node.

oddTail->next  = evenHead;  // Insert the even-numbered list head after the odd-numbered list tail
evenTail->next = nullptr;   // Even list ends point to null
Copy the code

Time complexity analysis: The whole list is traversed only once, so the time complexity is O(n)O(n)O(n). The traversal only records constant extra Pointers, so the extra space complexity is O(1)O(1)O(1) O(1).

C++ code

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; * /
class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if(! head || ! head->next)return head;
        auto oddHead  = head, oddTail = oddHead;  // Define four linked list Pointers
        auto evenHead = head->next, evenTail = evenHead;

        for(ListNode* p = head->next->next; p;)
        {
            oddTail = oddTail->next = p;
            p = p->next;
            if(p) // The current node is not empty
            {
                evenTail = evenTail->next = p;
                p = p->next;
            }
        }
        oddTail->next  = evenHead; // Insert the even-numbered list head after the odd-numbered list tail
        evenTail->next = nullptr;
        returnoddHead; }};Copy the code

4. Java code

/** * 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) return head;
        ListNode oddHead  = head, oddTail = oddHead;  // Define four linked list Pointers
        ListNode evenHead = head.next, evenTail = evenHead;

        for(ListNode p = head.next.next; p! =null;)
        {
            oddTail = oddTail.next = p;
            p = p.next;
            if(p ! =null)
            {
                evenTail = evenTail.next = p;
                p = p.next;
            }
        }
        oddTail.next  = evenHead; // Insert the even-numbered list head after the odd-numbered list tail
        evenTail.next = null;
        returnoddHead; }}Copy the code

Original link: 328. Odd-even linked lists