首页 > 其他 > 详细

【Leetcode】328.奇偶链表

时间:2020-11-13 10:29:28      阅读:26      评论:0      收藏:0      [点我收藏+]

题目链接

328. 奇偶链表

题目描述

技术分享图片

解题思路

暴力法

先统计链表长度,然后根据链表长度决定两两交换链表中的元素的次数即可。(如果不明白自己画个图即可)

拆分为奇偶链表在拼接

维护两个指针 odd 和 even 分别指向奇数节点和偶数节点,初始时 odd = head,even = evenHead。通过迭代的方式将奇数节点和偶数节点分离成两个链表,每一步首先更新奇数节点,然后更新偶数节点。最后把偶数节点拼接在奇数节点后面即可。

AC代码

解法一

/**
 * 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 || head.next.next ==null) return head;
        ListNode countNode = head;
        int count = 0;
        while(countNode != null){
            count++;
            countNode = countNode.next;
        }
        //链表的经典解法,3指针!!!!!!
        ListNode dum = head;
        ListNode pre = head;
        ListNode cur = head.next;
        ListNode temp = cur.next;
        int tot = 0;
        //根据链表长度决定两两元素交换的次数
        if(count % 2 == 0) tot = count / 2 - 1;
        else tot = count / 2;
        while(tot > 0){
            int num = tot;
            while(num > 0){
                pre.next = temp;
                cur.next = temp.next;
                temp.next = cur;
                pre = cur;
                if(cur.next != null) cur = cur.next;
                if(cur.next != null) temp = cur.next;
                num--;
            }
            tot--;
            dum = dum.next;
            pre = dum;
            cur = pre.next;
            temp = cur.next;
        }
        return head;
    }
}

解法二

/**
 * 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 || head.next.next ==null) return head;
        ListNode odd = head;
        ListNode even = head.next;
        ListNode evenHead = even;
        while(true){
            odd.next = even.next;
            if(even.next != null) odd = even.next;
            else break;
            if(odd.next != null) even.next = odd.next;
            else break;
            if(odd.next != null) even = odd.next;
        }
        odd.next = evenHead;
        even.next = null;
        return head;
    }
}

【Leetcode】328.奇偶链表

原文:https://www.cnblogs.com/XDU-Lakers/p/13967697.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!