1. Add Two Numbers

https://leetcode.com/explore/interview/card/top-interview-questions-medium/107/linked-list/783/

merge lists with carry value:

  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* addTwoNumbers(ListNode* l1, ListNode* l2) {
  15.         ListNode* dummy = new ListNode(-1);
  16.         ListNode* curr = dummy;
  18.         int carry = 0;
  19.         while(l1 || l2){
  20.             int a = l1 ? l1->val : 0;
  21.             int b = l2 ? l2->val : 0;
  23.             curr->next = new ListNode((a + b + carry) % 10);
  24.             carry = (a + b + carry) / 10; //over 10, carry value is 1
  26.             l1 = l1 ? l1->next : NULL;
  27.             l2 = l2 ? l2->next : NULL;
  28.             curr = curr->next;
  29.         }
  31.         if(carry!=0) //if there is a carry value at last, add a new node of 1
  32.             curr->next = new ListNode(1);
  34.         return dummy->next;
  35.     }
  36. };

2. Odd Even Linked List

https://www.yuque.com/akiencore/yeyky8/pwh4fl/edit?toc_node_uuid=Ii4DR7VgEcE67yxq

2 lists, one jump from the last node of another one:

//CAUTION: it is talking about the node number and not the value in the nodes
class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if(!head || !head->next) return head;

        ListNode* odd = head;
        ListNode* even = head->next;
        ListNode* head2 = even;

        while(odd->next && even->next){ //if both have next
            odd->next = even->next;
            odd = odd->next;

            even->next = odd->next;
            even = even->next;
        }
        odd->next = head2;

        return head;
    }
};

3. Intersection of Two Linked Lists

https://leetcode.com/explore/interview/card/top-interview-questions-medium/107/linked-list/785/

“switch”:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* curr1 = headA;
        ListNode* curr2 = headB;
        int switched1 = 0;
        int switched2 = 0;

        while(curr1 && curr2){
            if(curr1 == curr2) return curr1;

            curr1 = curr1->next;
            curr2 = curr2->next;

            if(!curr1 && !curr2)
                break;

            if(!curr1 && switched1 == 0){
                curr1 = headB;
                switched1 = 1;
            } else if(!curr1 && switched1 == 1){
                curr1 = headA;
                switched1 = 0;
            }

            if(!curr2 && switched2 == 0){
                curr2 = headA;
                switched2 = 0;
            } else if(!curr2 && switched2 == 1){
                curr2 = headB;
                switched2 = 1;
            }
        }

        return NULL;
    }
};
  • To simply explain, this idea is to let 2 curr nodes switch between each other if it meets an end
    • and they will meet if they have an intersection, before that, both curr nodes passed the same number of steps

2. Linked List - 图1
for example,
curr1 from A: 1-9-1-2-4-(null, turn to the head of B)3-2
curr2 from B: 3-2-4-(null, turn to the head of A)1-9-1-2

  • if no intersections at all, both nodes reach the end at the same time

2. Linked List - 图2
for example,
curr 1 from A: 2-6-4-(null, turn to the head of B)1-5-NULL
curr 2 from B: 1-5-(null, turn to the head of A)2-6-4-NULL