首页 > 其他 > 详细

Lintcode228-Middle of Linked List-Naive

时间:2019-04-21 20:36:14      阅读:115      评论:0      收藏:0      [点我收藏+]

228. Middle of Linked List

Find the middle node of a linked list.

Example

Example 1:

Input:  1->2->3
Output: 2	
Explanation: return the value of the middle node.

Example 2:

Input:  1->2
Output: 1	
Explanation: If the length of list is even return the value of center left one.	

Challenge

If the linked list is in a data stream, can you find the middle without iterating the linked list again?

 

看着简单,但需要思路缜密。

考虑两种情况:

case 1: 空链表 (要确保head不是一个空结点,否则, while(head.next) 就会抛出空指针异常! 记住:写head.next之前一定要排除空结点的情况!!!!!!!!!!

case 2: 链表不为空 (快慢指针)

快慢指针同时指向头结点,慢指针(result)走一步,快指针(head)走两步。

1)如果链表有偶数个结点,那么,当快指针  head.next.next == null 时 (事件A)

2)如果链表有奇数个结点,那么,当快指针  head.next == null 时 (事件B)

返回慢指针指向的结点(事件C)

当上面两种情况都不发生时,慢指针(result)走一步,快指针(head)走两步。(Not C)

 

即:C = A || B, 那么 Not C = !A && !B

 

WARNING!

while (head.next != null && head.next.next != null)   不能写成 while (head.next.next != null && head.next != null)  

因为如果是奇数结点的链表(1->2->3->null)当慢指针指向2时,快指针指向3。下一次循环如果先判断head.next.next 就会抛出空指针异常,所以应该先检验head.next是否为空,不满足(就不会执行第二个布尔表达式)直接退出循环。

 

代码:

public ListNode middleNode(ListNode head) {
    ListNode result = head;
    if (head == null) {
        return result;
    }
    while (head.next != null && head.next.next != null) {
        result = result.next;
        head = head.next.next;
    }
    return result;
}

 

Lintcode228-Middle of Linked List-Naive

原文:https://www.cnblogs.com/Jessiezyr/p/10746549.html

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