Re: [閒聊] LeetCode 876

[sustainer123 (caster )]

※ 引述《sustainer123 (caster )》之銘言：
: 876. Middle of the Linked List
: 給你一個linked list，請找出它的middle node，
: 如長度為偶數，中間有二middle node，則取第二個。
: Example 1:
: Input: head = [1,2,3,4,5]
: Output: [3,4,5]
: Explanation: The middle node of the list is node 3.
: Input: head = [1,2,3,4,5,6]
: Output: [4,5,6]
: Explanation: Since the list has two middle nodes with values 3 and 4, we
: return the second one.
: 思路:
: linked list無法直接得知長度，所以先設另一linked list為i，使i=head，
: 將i跑完一遍，便能得知長度。
: 之後將長度/2，為了使小數點進位，所以加上round()函式。
: 最後用迴圈跑出middle node，回傳head。
: C Code
: -------------------------
: /**
:  * Definition for singly-linked list.
:  * struct ListNode {
:  *     int val;
:  *     struct ListNode *next;
:  * };
:  */
: #include <math.h>
: struct ListNode* middleNode(struct ListNode* head){
:     struct ListNode* i = head;
:     int length = 0;
:     while( i != NULL){
:         i = i->next;
:         length++;
:     }
:     int middle = round(length/2);
:     int cur=0;
:     while(cur < middle){
:         head = head->next;
:         cur++;
:     }
:     return head;
: }
: --------------------------

思路二:
使用fast & slow pointer，先設兩個linklist=head，slow每次只走一步，
fast每次走兩步，fast走完時，slow正好到一半的地方。
這解法的好處是只需要走一遍linklist。

此外，這題必須要考慮linklist長度的奇偶數問題，
假設為奇數，slow剛好落在一半的位子。
假設為偶數，slow會落在middle node-1的位子，所以回傳時要slow->next。

C Code
--------------------

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* middleNode(struct ListNode* head){
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    while(fast->next != NULL && fast->next->next != NULL){
        slow = slow->next;
        fast = fast->next->next;
    }
    return(fast->next == NULL)?slow:slow->next;
}
---------------------


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.137.115.119 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1672999500.A.9EA.html
→ MurasakiSion: 你while裡面怎麼還是從head開始 這樣哪有往前        01/06 18:06
推 Jaka: 你loop裡面寫錯了 這樣永遠只會是head->next                 01/06 18:06
→ sustainer123: 阿 我找到問題了 用head會出包
推 SecondRun: 你每次都從head走捏                                   01/06 18:07
＠ 以上紅底標記3位，每人50P(稅前)發送完成!   by AutoGiveP 2.12
→ sustainer123: 感謝賽恩跟jaka
→ sustainer123: 對 剛才寫很順沒發現
※ 編輯: sustainer123 (223.137.115.119 臺灣), 01/06/2023 18:09:38
→ mpyh12345: 大師
※ 編輯: sustainer123 (223.137.115.119 臺灣), 01/06/2023 18:24:05