一、题目

力扣原题：

二、额外开辟空间

/** * 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 (null == head) {            return null;        }        // 保存奇数节点        List
   
     oddNodes = new ArrayList<>();        ListNode odd = head;        while (null != odd) {            oddNodes.add(odd);            if (null == odd.next) {                break;            }            odd = odd.next.next;        }        // 保存偶数节点        List
    
      evenNodes = new ArrayList<>();        ListNode even = head.next;        while (null != even) {            evenNodes.add(even);            if (null == even.next) {                break;            }            even = even.next.next;        }                ListNode root = new ListNode(-1);        ListNode cur = root;        for (ListNode oddNode : oddNodes) {            cur.next = new ListNode(oddNode.val);            cur = cur.next;        }        for (ListNode evenNode : evenNodes) {            cur.next = new ListNode(evenNode.val);            cur = cur.next;        }        return root.next;    }}

时间复杂度：O(n)

空间复杂度：O(n)

三、双指针

/** * 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 (null == head) {            return null;        }        // 奇数节点        ListNode odd = head;        // 偶数节点        ListNode even = head.next;        // 保存头节点        ListNode oddRoot = odd;        ListNode evenRoot = even;        while (null != even) {            // 计算并连接下一个奇数节点            ListNode nextOdd = even.next;            odd.next = nextOdd;            // 计算并连接下一个偶数节点            if (null != even.next) {                ListNode nextEven = even.next.next;                even.next = nextEven;            }            // 连接链表            if (null != odd.next) {                odd = odd.next;            }            odd.next = evenRoot;            even = even.next;        }        return oddRoot;    }}