4. Linked List Solutions

  1. and 2. will be implemented in next chapter.

  1. You can add these two lines to linked list implementation as prototype for implementation for iterative and recursive version.

    void reverse(ll**);
    void rreverse(ll**, ll*);
    

    The most important thing is to be able to think how we are going to do the implementation. Let us first take the case of non-recursive part. We can visualize the linked list as nodes attached with pointers. So all we have to do is make head point to the last node. We reverse the pointer. Now since the pointer is broken we need to maintain two pointers the current node and the next node, hence, we will need two extra pointers. Now as next pointer is broken we can keep assigning current pointer to it as shown in the diagram below:

    The equivalent code for the above can be written as:

    void reverse(ll** head)
    {
        ll *next = NULL;
        ll *current = NULL;
    
        if(!(*head))
            return;
    
        while((*head)->next != NULL)
        {
            next = (*head)->next;
            (*head)->next = current;
            current = *head;
            (*head) = next;
        }
        (*head)->next = current;
    }
    

    Notice that when we reach the end of node the pointer next will be in broken state and therefore from last pointer whose next would be pointing NULL must be made to point to current node as shown. The entire process is shown in the diagram below(we start with a list having three nodes 10, 20 and 30. Again see the image form bottom to top.):

    System Message: WARNING/2 (\node at(0, 0) [rectangle, draw] (A) {20}; \node at(2, 0) [rectangle, draw] (B) {30}; \node at(-2, 0) [rectangle, draw] (C) {10}; \draw [->, >=stealth] (C.east) -- (A.west); \draw [->, >=stealth] (A.east) -- (B.west); \draw [->, >=stealth] (B.east) -- ++(1, 0); \draw [<-, >=stealth] (C.west) -- ++(-1, 0); \node at ($(B.east)+(1.7, 0)$) {$NULL$}; \node at ($(C.west)-(1.7, 0)$) {$*head$}; \node at ($(C.east)+(.5, .2)$) {next}; \node at ($(A.east)+(.5, .2)$) {next}; \node at ($(B.east)+(.5, .2)$) {next}; \node [label={[align=center, yshift=-1.3cm]Initially we have three nodes in linked list.}] (F) {};)

    !pdftoppm command cannot be run

System Message: WARNING/2 (\node at(0, 0) [rectangle, draw] (A) {20}; \node at(2, 0) [rectangle, draw] (B) {30}; \node at(-2, 0) [rectangle, draw] (C) {10}; \node at(0, 1.5) (D) {$next$}; \draw [->, >=stealth] (C.east) -- (A.west); \draw [->, >=stealth] (A.east) -- (B.west); \draw [->, >=stealth] (B.east) -- ++(1, 0); \draw [<-, >=stealth] (C.west) -- ++(-1, 0); \draw [->, >=stealth] (D.south) -- (A.north); \node at ($(B.east)+(1.7, 0)$) {$NULL$}; \node at ($(C.west)-(1.7, 0)$) {$*head$}; \node at ($(C.east)+(.5, .2)$) {next}; \node at ($(A.east)+(.5, .2)$) {next}; \node at ($(B.east)+(.5, .2)$) {next}; \node [label={[align=center, yshift=-1.3cm]In the while loop $next$ variable points to $(*head)->next$.}] (F) {};)

!pdftoppm command cannot be run

System Message: WARNING/2 (\node at(0, 0) [rectangle, draw] (A) {20}; \node at(2, 0) [rectangle, draw] (B) {30}; \node at(-2, 0) [rectangle, draw] (C) {10}; \node at(0, 1.5) (D) {$next$}; \draw [->, >=stealth] (C.east) -- ($(A.west)!.5!(C.east)$) -- ($(A.west)!.5!(C.east)$) -- ++(0, -.5); \draw [->, >=stealth] (A.east) -- (B.west); \draw [->, >=stealth] (B.east) -- ++(1, 0); \draw [<-, >=stealth] (C.west) -- ++(-1, 0); \draw [->, >=stealth] (D.south) -- (A.north); \node at ($(B.east)+(1.7, 0)$) {$NULL$}; \node at ($(C.west)-(1.7, 0)$) {$*head$}; \node at ($(C.east)+(.5, .2)$) {next}; \node at ($(A.east)+(.5, .2)$) {next}; \node at ($(B.east)+(.5, .2)$) {next}; \node at ($(A.west)!.5!(C.east)+(0, -.8)$) {$NULL$}; \node [label={[align=center, yshift=-1.8cm]$(*head)->next$ is assigned $current$ which is $NULL$.}] (F) {};)

!pdftoppm command cannot be run