LeetCode 328. Odd Even Linked List

Problem

LeetCode 328. Odd Even Linked List

1. 题目简述

给出一个链表，将所有奇数个节点串起来，然后接上所有偶数位的节点。这里说的是节点的index而不是节点的value。例如：

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

2. 算法思路

链表+双指针

这道题不知道为什么划分到medium中，相当于将链表重新排序。这里要用到两个指针，一个指向当前odd的结尾，一个指向even的结尾，注意赋值顺序即可。

3. 解法

注意推导，过程，算法本身并不难

/**
 * 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 odd = head, even = head.next;

        while (even != null && even.next != null) {
            ListNode odd_next_node = even.next;
            ListNode even_next_node = odd_next_node.next;
            ListNode even_start_node = odd.next;

            odd.next = odd_next_node;
            odd = odd.next;
            even.next = even_next_node;
            even = even.next;
            odd.next = even_start_node;
        }

        return head;
    }
}