首页 > 其他 > 详细

143. Reorder List - LeetCode

时间:2018-07-16 00:16:16      阅读:234      评论:0      收藏:0      [点我收藏+]

Question

143. Reorder List

技术分享图片

Solution

题目大意:给一个链表,将这个列表分成前后两部分,后半部分反转,再将这两分链表的节点交替连接成一个新的链表

思路 :先将链表分成前后两部分,将后部分链表反转,再将两部分链表连接成一个新链表

Java实现:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) return;
        
        ListNode mid = findMid(head);
        ListNode l2 = mid.next;
        mid.next = null; // 将前半部分链表截断
        l2 = reverse(l2); // 将后半部分链表反转
        ListNode l1 = head;
        // 组装新的链表
        while (l1 != null && l2 != null) {
            ListNode tmp = l1.next;
            l1.next = l2;
            l2 = l2.next;
            l1.next.next = tmp;
            l1 = tmp;
        }
    }
    
    // 返回链表的中间节点
    ListNode findMid(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
    
    // 返回反转后的链表
    ListNode reverse(ListNode head) {
        ListNode newHead = null;
        while (head != null) {
            ListNode tmp = head.next;
            head.next = newHead;
            newHead = head;
            head = tmp;
        }
        return newHead;
    }
}

143. Reorder List - LeetCode

原文:https://www.cnblogs.com/okokabcd/p/9315638.html

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