题目链接

微信文章

题目描述

给定一个奇数位升序，偶数位降序的链表，将其重新排序。

输入: 1->8->3->6->5->4->7->2->NULL
输出: 1->2->3->4->5->6->7->8->NULL

解题思路

方法一：拆分

1. 将链表按奇数偶数拆分
2. 将偶数链表反转
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;
        }
        Pair<ListNode, ListNode> res = splitList(head);
        ListNode head1 = res.getKey(), head2 = res.getValue();
        head2 = reverseList(head2);
        return mergeList(head1,head2);
    }
    // 拆分链表
    private Pair<ListNode, ListNode> splitList(ListNode head){
        ListNode head1 = head;
        ListNode head2 = head.next;
        ListNode cur1 = head1, cur2 = head2;
        boolean flag = true;
        head = head.next.next;
        while(head!=null){
            if(flag){
                cur1.next = head;
                cur1 = head;
            }else{
                cur2.next = head;
                cur2 = head;
            }
            flag = !flag;
            head = head.next;
        }
        cur1.next = null;
        cur2.next = null;
        // Pair<ListNode, ListNode> res = new Pair<>(head1,head2);
        return new Pair<>(head1,head2);
    }
    // 反转链表 头插法
    private ListNode reverseList(ListNode head){
        // 头插法
        ListNode hair = new ListNode();
        while(head != null){
            ListNode node = head;
            head = head.next;
            node.next = hair.next;
            hair.next = node;
        }
        return hair.next;
    }
    // 合并链表
    private ListNode mergeList(ListNode head1, ListNode head2){
        ListNode hair = new ListNode();
        ListNode cur = hair;
        while(head1 != null && head2 != null){
            if(head1.val < head2.val){
                cur.next = head1;
                head1 = head1.next;
            }else{
                cur.next = head2;
                head2 = head2.next;
            }
            cur = cur.next;
        }
        if(head1 != null){
            cur.next = head1;
        }
        if(head2 != null){
            cur.next = head2;
        }
        return hair.next;
    }
   }
   

• 时间复杂度 O(n^2)
• 空间复杂度 O(1)