领扣LintCode算法问题答案-99. 重排链表

目录

99. 重排链表描述样例 1：样例 2： 题解鸣谢

99. 重排链表

描述

给定一个单链表L: L0→L1→…→Ln-1→Ln,

重新排列后为：L0→Ln→L1→Ln-1→L2→Ln-2→…

必须在不改变节点值的情况下进行原地操作。

样例 1：

输入: 1->2->3->4->null 输出: 1->4->2->3->null

样例 2：

输入: 1->2->3->4->5->null 输出: 1->5->2->4->3->null

题解

/** * Definition for ListNode * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { /** * @param head: The head of linked list. * @return: nothing */ public void reorderList(ListNode head) { // write your code here if (head == null || head.next == null) { return; } ListNode mid = findMiddle(head); ListNode tail = reverse(mid.next); mid.next = null; merge(head, tail); } private void merge(ListNode head1, ListNode head2) { ListNode dummy = new ListNode(0); while (head1 != null && head2 != null) { dummy.next = head1; head1 = head1.next; dummy = dummy.next; dummy.next = head2; head2 = head2.next; dummy = dummy.next; } if (head1 != null) { dummy.next = head1; } else { dummy.next = head2; } } private ListNode findMiddle(ListNode head) { ListNode slow = head, fast = head.next; while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; } return slow; } private ListNode reverse(ListNode head) { ListNode newHead = null; while (head != null) { ListNode temp = head.next; head.next = newHead; newHead = head; head = temp; } return newHead; } }

原题链接点这里

鸣谢

非常感谢你愿意花时间阅读本文章，本人水平有限，如果有什么说的不对的地方，请指正。 欢迎各位留言讨论，希望小伙伴们都能每天进步一点点。