1. Delete Node in a Linked List

https://leetcode.com/explore/interview/card/top-interview-questions-easy/93/linked-list/553/

move the next value into the current one, and delete the next one

  • 2 constraints related to this method:

    • The node to be deleted is in the list and is not a tail node

    • I can modify the value in a node

      1. /**
      2. * Definition for singly-linked list.
      3. * struct ListNode {
      4. *     int val;
      5. *     ListNode *next;
      6. *     ListNode(int x) : val(x), next(NULL) {}
      7. * };
      8. */
      9. class Solution {
      10. public:
      11. void deleteNode(ListNode* node) {
      12.    ListNode* del = node->next;
      13.    node->val = del->val;
      14.    node->next = del->next;
      16.    delete del;
      17. }
      18. };

2. Remove Nth Node From End of List

https://leetcode.com/explore/interview/card/top-interview-questions-easy/93/linked-list/603/

runner and chaser method:

  1. /**
  2.  * Definition for singly-linked list.
  3.  * struct ListNode {
  4.  *     int val;
  5.  *     ListNode *next;
  6.  *     ListNode() : val(0), next(nullptr) {}
  7.  *     ListNode(int x) : val(x), next(nullptr) {}
  8.  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
  9.  * };
  10.  */
  11. class Solution {
  12. public:
  13.     ListNode* removeNthFromEnd(ListNode* head, int n) {
  14.         ListNode* dummy = new ListNode();
  15.         dummy->next = head;
  16.         ListNode* runner = dummy;
  17.         ListNode* chaser = dummy;
  19.         for(int i = 0; i < n; i++){
  20.             runner = runner->next;
  21.         }
  23.         while(runner->next){
  24.             chaser = chaser->next;
  25.             runner = runner->next;
  26.         }
  28.         ListNode* del = chaser->next;
  29.         chaser->next = chaser->next->next;
  31.         delete del;
  33.         return dummy->next;
  34.     }
  35. };

3. Reverse Linked List

https://leetcode.com/explore/interview/card/top-interview-questions-easy/93/linked-list/560/

reassign next pointers:

  1. /**
  2.  * Definition for singly-linked list.
  3.  * struct ListNode {
  4.  *     int val;
  5.  *     ListNode *next;
  6.  *     ListNode() : val(0), next(nullptr) {}
  7.  *     ListNode(int x) : val(x), next(nullptr) {}
  8.  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
  9.  * };
  10.  */
  11. class Solution {
  12. public:
  13.     ListNode* reverseList(ListNode* head) {
  14.         ListNode* prev = NULL;
  15.         ListNode* curr = head;
  17.         while(head){
  18.             head = head->next;
  20.             curr->next = prev;
  21.             prev = curr;
  22.             curr = head;
  23.         }
  25.         return prev;
  26.     }
  27. };

4. Merge Two Sorted Lists

https://leetcode.com/explore/interview/card/top-interview-questions-easy/93/linked-list/771/

create a new list:

  1. /**
  2.  * Definition for singly-linked list.
  3.  * struct ListNode {
  4.  *     int val;
  5.  *     ListNode *next;
  6.  *     ListNode() : val(0), next(nullptr) {}
  7.  *     ListNode(int x) : val(x), next(nullptr) {}
  8.  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
  9.  * };
  10.  */
  11. class Solution {
  12. public:
  13.     ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
  14.         ListNode* dummy = new ListNode(-1);
  15.         ListNode* curr = dummy;
  17.         while(l1 && l2){
  18.             if(l1->val <= l2->val){
  19.                 curr->next = new ListNode(l1->val);
  20.                 l1 = l1->next;
  21.                 curr = curr->next;
  22.             } else {
  23.                 curr->next = new ListNode(l2->val);
  24.                 l2 = l2->next;
  25.                 curr = curr->next;
  26.             }
  27.         }
  29.         if(l1){
  30.             curr->next = l1;
  31.         }
  33.         if(l2){
  34.             curr->next = l2;
  35.         }
  37.         return dummy->next;
  38.     }
  39. };

sort in-place:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* head;
        ListNode* curr;

        if(l1 && !l2){
            return l1;
        } else if(!l1 && l2){
            return l2;
        } else if(!l1 && !l2){
            return NULL;
        }

        if(l1->val <= l2->val){
            head = l1;
            curr = head;
            l1 = l1->next;
            head->next = NULL;
        }
        else{
            head = l2;
            curr = head;
            l2 = l2->next;
            head->next = NULL;
        }

        while(l1 && l2){
            if(l1->val <= l2->val){
                curr->next = l1;
                curr = curr->next;
                l1 = l1->next;
                curr->next = NULL;
            } else {
                curr->next = l2;
                curr = curr->next;
                l2 = l2->next;
                curr->next = NULL;
            }
        }

        if(l1){
            curr->next = l1;
        }

        if(l2){
            curr->next = l2;
        }

        return head;
    }
};

5. Palindrome Linked List

https://leetcode.com/explore/interview/card/top-interview-questions-easy/93/linked-list/772/

change list into string, and apply 2 pointers:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        string s = "";

        while(head){
            s += head->val + '0';
            head = head->next;
        }

        int l = 0;
        int r = s.length() - 1;

        while(l < r){
            if(s[l] != s[r])
                return false;

            l++;
            r--;
        }

        return true;
    }
};

6. Linked List Cycle

https://leetcode.com/explore/interview/card/top-interview-questions-easy/93/linked-list/773/

runner and chaser:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode* runner = head;
        ListNode* chaser = head;

        while(runner){
            runner = runner->next;
            if(runner)
                runner = runner->next;
            chaser = chaser->next;

            if(runner == chaser && runner != NULL)
                return true;
        }

        return false;
    }
};