LeetCode Blind 75 - Part 3

15 Jun 2021

In this blog I’ll be posting the codes (C++) and hints for the Linked List related questions. You can find the link to the curated Blind-75 link here.

1. Reverse a linked list

Problem Given the head of a singly linked list, reverse the list, and return the reversed list.

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = NULL;
        ListNode* curr = head;
        ListNode* nxt = head;
        while(nxt!=NULL){
            nxt = nxt ->next;
            curr->next = prev;
            prev = curr;
            curr = nxt;
        }
        return prev;
        
    }
};

2. LinkedList Cycle

Problem Given head, the head of a linked list, determine if the linked list has a cycle in it.
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.
Return true if there is a cycle in the linked list. Otherwise, return false.

Hint: Two pointer method

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(head==NULL)
            return false;
        ListNode* slow = head;
        ListNode* fast = head->next;
        
        while(slow!=fast){
            if(fast==NULL || fast->next==NULL)
                return false;
            slow = slow ->next;
            fast = fast->next->next;
        }
        return true;
    }
};

3. Merge two sorted lists

Problem Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.

Hint: Recursion

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* result = NULL;
        if(l1==NULL){
            return l2;
        }
        if(l2==NULL){
            return l1;
        }
        
        if(l1->val <= l2->val){
            result = l1;
            result->next = mergeTwoLists(l1->next, l2);
        }
        else{
            result = l2;
            result->next = mergeTwoLists(l1, l2->next);
             }
        return result;
        
    }
};

4. Remove Nth Node From End of List

Problem Given the head of a linked list, remove the nth node from the end of the list and return its head.

Hint: Two pointer method

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {

        ListNode* fast = head;
        ListNode* slow = head;

        while(n--)
            fast = fast->next;
        if(fast==NULL)
            return head->next;
        while(fast->next!=NULL){
            fast=fast->next;
            slow=slow->next;   
        }
        slow->next= slow->next->next;
        return head;
    
    }
};

5. Reorder List

Problem You are given the head of a singly linked-list. The list can be represented as:

L0 → L1 → … → Ln - 1 → Ln
Reorder the list to be on the following form:

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
You may not modify the values in the list's nodes. Only nodes themselves may be changed.

Hint: Using the penultimate node to form the connections between different nodes

class Solution {
public:
    void reorderList(ListNode* head) {
        if(head==NULL || head->next==NULL || head->next->next==NULL)
            return;
        ListNode* p = head;
        while(p->next->next!=NULL){
            p=p->next;
        }
        p->next->next = head->next;
        head->next = p->next;
        p->next=NULL;
        reorderList(head->next->next);
    }
};

LeetCode Blind 75 - Part 3

Related Posts