[Data Structure] Single Linked List OJ Questions (2)

Article directory

• 1. Split linked list
• 2. Palindrome linked list
• 3. Intersection linked list
• 4. Circular linked list I
• • 5. Circular Linked List II
• 6. Deep copy of linked list

1. Split linked list

We create two linked lists, put the nodes smaller than x in one linked list, and the remaining nodes in the other, and finally connect the two linked lists. A linked list with sentinel bits is used here. There is no need to consider the problem of head insertion and the empty first linked list, which can greatly reduce the amount of code.

class Partition {<!-- -->
public:
    ListNode* partition(ListNode* pHead, int x) {<!-- -->
        struct ListNode* lessHead=(struct ListNode*)malloc(sizeof(struct ListNode));
        struct ListNode* lesstail=lessHead;
        struct ListNode* greaterHead=(struct ListNode*)malloc(sizeof(struct ListNode));
        struct ListNode* greatertail=greaterHead;
        struct ListNode* cur=pHead;
        while(cur)
        {<!-- -->
            if(cur->val < x)
            {<!-- -->
                lesstail->next=cur;
                lesstail=cur;
            }
            else
            {<!-- -->
                greatertail->next=cur;
                greatertail=cur;
            }
            cur=cur->next;
        }
        greatertail->next=NULL;
        lesstail->next=greaterHead->next;
        free(greaterHead);
        struct ListNode* newnode=lessHead->next;
        free(lessHead);
        return newnode;
    }
};

Note: The pointer field of the last node of the linked list must be set to empty, otherwise it will cause the linked list to cycle.

2. Palindrome linked list

Idea: First find the middle address (odd number) or the second address (even number) in the middle of the linked list as the head of the second linked list, then reverse the second linked list, and then The original linked list is compared with the second linked list. (When either the original linked list or the second linked list is empty, you can break out of the loop, indicating that it is a palindrome linked list.

struct ListNode* MidNode(struct ListNode* Head)
{<!-- -->
    struct ListNode* slow=Head,*fast=Head;
    while(fast & amp; & amp;fast->next)
    {<!-- -->
        slow=slow->next;
        fast=fast->next->next;
    }
    return slow;
}

struct ListNode* RevNode(struct ListNode* Head)
{<!-- -->
    struct ListNode* prev=NULL,*cur=Head;
    while(cur)
    {<!-- -->
        struct ListNode* next=cur->next;
        cur->next=prev;
        prev=cur;
        cur=next;
    }
    return prev;
}

class PalindromeList {<!-- -->
public:
    bool chkPalindrome(ListNode* A) {<!-- -->
        // write code here
        struct ListNode* B=MidNode(A);
        B=RevNode(B);
        while(A & amp; & amp;B)
        {<!-- -->
            if(A->val==B->val)
            {<!-- -->
                A=A->next;
                B=B->next;
            }
            else {<!-- -->
            return false;
            }
        }
        return true;
    }
};

3. Intersecting linked lists

Idea 1: Each node in the A linked list is compared with the B linked list in sequence. If there is equality, it is an intersection. The first one that is equal is the intersection point.

(Determine whether it intersects and what is the intersection point) Time complexity: O(M*N)

Idea 2: When the addresses of the tail nodes are the same, it means intersection. (Determine whether it is an intersection)

Find the length of the two linked lists, and then the longer linked list first takes the difference between the two linked lists, and then the two linked lists are walked together. When the addresses are the same, the position is the node (what is the intersection point). Time complexity: O(M + N)

truct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {<!-- -->
    struct ListNode* curA=headA,*curB=headB;
    int lenA=0,lenB=0;
    while(curA->next)
    {<!-- -->
        curA=curA->next;
        lenA + + ;
    }
    while(curB->next)
    {<!-- -->
        curB=curB->next;
        lenB + + ;
    }
    if(curA!=curB)
        return NULL;
    int gap=abs(lenA-lenB);
    struct ListNode* shortList = headA;
    struct ListNode* longList = headB;
    if(lenA>lenB)
    {<!-- -->
        shortList=headB;
        longList=headA;
    }
    while(gap--)
    {<!-- -->
        longList=longList->next;
    }
    while(longList & amp; & amp;shortList)
    {<!-- -->
        if(longList==shortList)
            return shortList;
        longList=longList->next;
        shortList=shortList->next;
    }
    return NULL;

}

Note:

• The addresses are the same, not the values (equal values are not necessarily nodes)

• The compiler executes a syntax error, and the compiler cannot check the execution logic, so return NULL must be added at the end (because there is an if above and then a value is returned, the compiler will think that there is no return value when the if condition is not met) ;

4. Circular linked list I

[Slow and fast pointer] slow takes one step at a time, and fast takes two steps at a time. When slow enters the loop, the catch-up mode is turned on, and finally fast catches up with slow; fast->next or fast will be NULL without the loop, and it will not be with the loop. will be NULL;

bool hasCycle(struct ListNode* head) {<!-- -->
    struct ListNode* slow = head, * fast = head;
    while (fast & amp; & amp; fast->next)
    {<!-- -->
        fast = fast->next->next;
        slow = slow->next;
        if (slow == fast)
        {<!-- -->
            return true;
        }
    }
    return false;
}

Note: fast is equal to slow at the beginning, so the value is assigned first and then compared in the loop

• Slow takes one step at a time, fast takes two steps at a time, and you can definitely catch up.

  When slow is halfway through, fast starts to enter the ring. At this time, the distance between the two is N. After each time, the distance will be reduced by 1, so you can definitely catch up. [Distance is 0, catch up]

• Slow takes one step at a time, fast takes three steps at a time, so you may not be able to catch up.

  When slow goes 1/3, fast starts to enter the ring. At this time, the distance between the two is N. After each time, the distance will be reduced by 2. If the distance is an odd number, it will be missed. [Even numbers can catch up]. At this time, the distance is -1. [Even numbers can catch up, and odd numbers can catch up. You can never catch up], so you may not be able to catch up.

5. Circular linked list II

Assume that the distance before entering the ring is L; the distance traveled by slow after entering the ring is x; the distance between the two after entering the ring is N; the length of the ring is C [fast and slow pointer] slow takes one step at a time, fast Taking two steps at a time, fast is twice as long as slow [slow will never be caught up by fast after walking a circle, but will be caught up by fast without walking around, because when slow enters the ring, the distance between the two is N, N must be smaller than the number of rings, so when the two meet, slow must not have completed a circle, so the distance traveled by slow is the distance L before entering the ring + the distance traveled by slow before and after entering the ring x after the two meet, that is L + x; the distance traveled by fast is n*C + L + x; n*C + L + x=2(L + x),—->n*C=L + x;n is an unknown number]【 After slow enters the ring, it is impossible for fast to complete a circle] n*C=L + x: It can be proved that one walks from entering the linked list and the other walks from the node where they meet, and slow and fast meet at the entrance of the ring.

struct ListNode *detectCycle(struct ListNode *head) {<!-- -->
    if(head==NULL || head->next==NULL)
        return NULL;
    struct ListNode* slow=head,*fast=head;
    while(fast & amp; & amp;fast->next)
    {<!-- -->
        slow=slow->next;
        fast=fast->next->next;
        if(slow==fast)
        {<!-- -->
            struct ListNode* meet=slow;
            while(slow!=head)
            {<!-- -->
                slow=slow->next;
                head=head->next;
            }
            return slow;
        }
    }
    return NULL;
}

6. Deep copy of linked list

truct Node* copyRandomList(struct Node* head) {<!-- -->
struct Node* cur =head;
    while(cur)
    {<!-- -->
        struct Node* copy=(struct Node*)malloc(sizeof(struct Node));
        struct Node* next=cur->next;
        cur->next=copy;
        copy->val=cur->val;
        copy->next=next;
        cur=next;
    }
    cur=head;
    while(cur)
    {<!-- -->
        struct Node* copy=cur->next;
        if(cur->random!=NULL)
        {<!-- -->
            copy->random=cur->random->next;
        }
        else
        {<!-- -->
            copy->random=NULL;
        }
        cur=copy->next;
    }
    cur=head;
    struct Node* copyHead=NULL;
    struct Node* copyTail=NULL;
    while(cur)
    {<!-- -->
        struct Node* copy=cur->next;
        struct Node* next=copy->next;
        if(copyTail==NULL)
        {<!-- -->
            copyHead=copyTail=copy;
        }
        else
        {<!-- -->
            copyTail->next=copy;
            copyTail=copyTail->next;
        }
        cur->next=next;
        cur=cur->next;
    }
    return copyHead;
}

Idea: Copy each node and connect it to the original node, link the random of the copied node, and the new random is next to the previous random. Finally, unzip the copied nodes and link them. [Index starts from 0]

This content ends here. I hope you can gain something from reading this, and thank you all for your support. If you have any questions about the article, you can leave a message in the comment area. Xiaoyang will definitely revise it carefully and write a better article~~