LeetCode::LinkedList(Part2)-Modifying the List

Introduction

---

Most linked list algorithms are logially quite straightforward. The main difficult lies in that fact that when working on a node in the list, often times you also need to have reference to the node just before it or after it. Take for example a simple case of deleting the node B from list A->B->C. After you identify where B is, you still need to keep a reference of A in order to write A->next = B->next.

This brings code complexity, as you need to keep track of more variables and treat special cases carefully. The head node obviously has no previous node and the NULL node has no node after it. I usually approach a problem in the following steps:

1. Design the inside of while loop

   In this step we ignore edge cases and focus on how to modify the body of the list. A cur node, initialized as the head node before we enter the loop, will always be the current node that we are working on.

2. Decide the break point for the loop

   This will usually be when our cur node reaches NULL, but exceptions exsist. For example, if we referencedcur->next->value in the loop, since a NULL node has no value filed, we must break out of the loop when cur->next is NULL.

3. Handle edge cases

   The head node usually needs to be handled seperately.

83. Remove Duplicates from Sorted List

Given a sorted linked list, delete all duplicates such that each element appear only once.

Example:

Input: 1->1->2->3->3
Output: 1->2->3

Solution 1 (Iterative)

ListNode* deleteDuplicates(ListNode* head) {
    ListNode *cur = head;
    while (cur && cur->next) {
        if (cur->val == cur->next->val)
            cur->next = cur->next->next;

        cur = cur->next;
    }
    return head;
}

Solution 2 (Recursive)

struct ListNode* deleteDuplicates(struct ListNode* head) {
    if (head == NULL || head->next == NULL)
        return head;
    
    struct ListNode* rest = deleteDuplicates(head->next);
    if (head->val == rest->val){
        // return rest;
        head->next = rest->next;
        return head;
    }
    else
        return head;
}

328. Odd Even Linked List

Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node index and not the value in the nodes.

Example:

Input: 1->2->3->4->5->NULL
Output: 1->3->5->2->4->NULL

Note:

• The relative order inside both the even and odd groups should remain as it was in the input.
• The first node is considered odd, the second node even and so on
• You should try to do it in place.

Solution

1. loop

first-> next = first->next->next can we do it in two passes? No so add second whats the break point whats the base case

When you need the node Before cur

---

82. Remove Duplicates from Sorted List II

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

Example:

Input: 1->2->3->3->4->4->5
Output: 1->2->5

Solution 1 (Iterative)

struct ListNode* deleteDuplicates(struct ListNode* head){
    struct ListNode dummy = {-1, head};
    struct ListNode* pre = &dummy;
    struct ListNode* cur = head;
    
    while(cur && cur->next){
        if (cur->val == cur->next->val){
            while(cur->next && cur->next->val == cur->val){
                cur = cur->next;
            }
            pre->next = cur->next;
        }
        else{
            pre = pre->next;
        }
        cur = cur->next;
    }
    return dummy.next;
}

203. Remove Linked List Elements

Remove all elements from a linked list of integers that have value val.

Example:

Input: 1->2->6->3->4->5->6, val = 6
Output: 1->2->3->4->5

Solution 1

struct ListNode* removeElements(struct ListNode* head, int val) {
    struct ListNode dummy = {-1, head};
    struct ListNode* pre = &dummy;
    struct ListNode* cur = head;
    
    while(cur){
        if (cur->val == val){
            pre->next = cur->next;
        }
        else{
            pre = pre->next;
        }
        cur = cur->next;
    }
    return dummy.next;
}

When you need nodes Before and After cur

---

put struct ListNode* after in the loop, so your while loop doesnt break.

206. Reverse Linked List

Reverse a singly linked list.

Example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

Solution 1 (Iterative)

When you need the node after temp

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* prev = NULL;
    struct ListNode* cur = head;
   
    while (cur){
        struct ListNode* after = cur->next;
        cur->next = prev;

        prev = cur;
        cur = after;
    }
    return prev;
}

As you can see, although we have to change the loop condition accordingly, the logic works exactly the same.

The Python version of the same code is quite a bit shorter:

def reverseList(head):
    pre, cur = None, head
    while cur:
        cur.next, pre, cur = pre, cur, cur.next
    return pre

This is the most popular solution on LeetCode, is 1 line shorter compared to using cur and nex, but perfonally I don’t like it much. Mainly because such a use of pre is the most typical and may confuse people.

Solution 2 (Recursive)

struct ListNode* reverseList(struct ListNode* head) {
    if (head == NULL || head->next == NULL){
        return head;
    }
    
    struct ListNode* tail = reverseList(head->next);
    head->next->next = head;
    head->next = NULL;
    return tail;
}

After the first recursive call, we have:

1->2<-3<-4<-5
   ↓
  NULL 

while tail is at 5 and head still at 1. We fix the 1->2 link with (head->next)->next = head and add 1->NULL.

24. Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head.

You may not modify the values in the list’s nodes, only nodes itself may be changed.

Example:

Input: 1->2->3->4
Output: 2->1->4->3

Solution 1 (Iterative)

struct ListNode* swapPairs(struct ListNode* head){
    struct ListNode dummy = {-1, head};
    struct ListNode* pre = &dummy;
    struct ListNode* cur = head;
    
    while(cur && cur->next){
        struct ListNode* after = cur->next;
        cur->next = after->next;
        pre->next = after;
        after->next = cur;
        
        pre = pre->next->next;
        cur = pre->next;
        
    }
    return dummy.next;
}

Solution 2 (Recursive)

struct ListNode* swapPairs(struct ListNode* head) {
    if (head==NULL || head->next == NULL)
        return head;
    
    struct ListNode* rest = swapPairs(head->next->next);
    struct ListNode* newhead = head->next;
    newhead->next = head;
    head->next = rest;
    return newhead;
}