tags: Leetcode easy list pointer python c++

876. Middle of the Linked List

[題目連結:] https://leetcode.com/problems/middle-of-the-linked-list/description/

題目:

Given the head of a singly linked list, return the middle node of the linked list.

If there are two middle nodes, return the second middle node.

[圖片來源:] https://leetcode.com/problems/middle-of-the-linked-list/description/

解題想法:

• 此題為求List中最中間的node
• 使用快慢pointer
  • slow每次走一步
  • fast每次走兩步
  • while判斷fast and fast.next是否不為nullptr
  • 最後slow即為中間node

Python:

class ListNode():
    def __init__(self,val=0,next=None):
        self.val=val
        self.next=next
    def insert(self,node):
        if self.next==None:
            self.next=ListNode(node)
        else:
            self.next.insert(node)
    def printList(self):
        head=self
        res=[]
        while head:
            res.append(head.val)
            head=head.next
        print(res)

class Solution(object):
    def middleNode(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        slow=head
        fast=head
        while fast and fast.next:
            slow=slow.next
            fast=fast.next.next
        return slow

if __name__=='__main__':
    result=Solution()
    head=ListNode(1)
    head.insert(2)
    head.insert(3)
    head.insert(4)
    head.insert(5)
    head.printList()

    ans=result.middleNode(head) #[1, 2, 3, 4, 5]
    print(ans.val) #3

C++:

#include<bits/stdc++.h>
using namespace std;

struct ListNode{
    int val;
    ListNode *next;
    ListNode(): val(0), next(nullptr){}
    ListNode(int x): val(x), next(nullptr){}
};

void InsertNode(ListNode *head, int data){
    if (head->next==nullptr){
        ListNode *new_data=new ListNode(data);
        head->next=new_data;
    }
    else{
        InsertNode(head->next,data);
    }
}

void PrintList(ListNode *head){
    ListNode *tmp=head;
    vector<int> res;
    while (tmp){
        res.push_back(tmp->val);
        tmp=tmp->next;
    }
    for (auto node: res){
        cout<<node<<" ";
    }
    cout<<endl;
}

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode *slow=head;
        ListNode *fast=head;
        while (fast && fast->next){
            slow=slow->next;
            fast=fast->next->next;
        }
        return slow;
    }
};

int main(){
    Solution res;
    ListNode *head =new ListNode(1);
    InsertNode(head,2);
    InsertNode(head,3);
    InsertNode(head,4);
    InsertNode(head,5);
    InsertNode(head,6);
    PrintList(head);

    ListNode *ans=res.middleNode(head);
    cout<<ans->val<<endl;
    return 0;
}