Leetcode--Java--328. 奇偶链表

本文主要是介绍Leetcode--Java--328. 奇偶链表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

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

请尝试使用原地算法完成。你的算法的空间复杂度应为 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

思路

拼接奇偶链表

1. 单独设置奇数、偶数链表的头结点和尾结点，然后在扫描中来截取出拼接到各自对应的链表后面。
2. 最后要把奇链表和偶链表拼接起来，然后让偶数链表末尾指向空（不然会存在环报错）。

代码

/*** 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, odd = oddHead, evenHead = head.next;ListNode even = evenHead;for(ListNode p = head.next.next; p != null; ) {//取出放到奇数头链表下odd.next= p;odd = odd.next;p = p.next;//下一个位置是偶数，不为空就放到偶数链表那if (p != null) {even.next = p;even = even.next;p = p.next;}}//拼接奇偶数链表,让even指向空，不然就会存在环odd.next = evenHead;even.next = null;return oddHead;}
}

这篇关于Leetcode--Java--328. 奇偶链表的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---