Leetcode problem Solving (linked list class)

Linked list is a special linear structure, because it cannot be randomly accessed like array, so the problems related to linked list have their own characteristics. I call it threading a needle. In this chapter, we’ll take a look at how to thread a list.

Linked lists, threading needles between nodes

Both lists and arrays are linear structures, but the difference between lists and arrays is that arrays can access data randomly. Give the index. This element can be accessed quickly in O(1) time complexity. Linked lists can only start with ab initio Pointers.

Leetcode206. Reverse linked lists

thought

• Maintaining three Pointers
  • pre
  • cur
  • next

Public: ListNode* reverseList(ListNode* head) {ListNode* pre = NULL; ListNode* cur = head;while( cur ! = NULL ){ ListNode* next = cur->next; cur->next = pre; pre = cur; cur = next; }returnpre; }};Copy the code

Similar problems

• leetcode92 Reverse Linked List II

Inverts the elements of a linked list from m to n.

• For 1->2->3->4->5->NULL, m = 2, n = 4
• Return list 1->4->3->2->5->NULL
  • What if m and n exceed the range of linked lists?
  • What if m > n?

Test the linked list program

Write two functions to create and print lists based on arrays

    /// LinkedList Test Helper Functions
    ListNode* createLinkedList(int arr[], int n){
    
        if( n == 0 )
            return NULL;
    
        ListNode* head = new ListNode(arr[0]);
        ListNode* curNode = head;
        for( int i = 1 ; i < n ; i ++ ){
            curNode->next = new ListNode(arr[i]);
            curNode = curNode->next;
        }
    
        return head;
    }
    
    void printLinkedList(ListNode* head){
    
        ListNode* curNode = head;
        while( curNode ! = NULL ){ cout << curNode->val <<"- >";
            curNode = curNode->next;
        }
    
        cout<<"NULL"<<endl;
    
        return;
    }
    
    void deleteLinkedList(ListNode* head){
    
        ListNode* curNode = head;
        while( curNode ! = NULL ){ ListNode* delNode = curNode; curNode = curNode->next; delete delNode; }return;
    }
    

main.cpp:

    int main(){
    
        int arr[] = {1, 2, 3, 4, 5};
        int n = sizeof(arr)/sizeof(int);
    
        ListNode* head = createLinkedList(arr, n);
        printLinkedList(head);
    
        ListNode* head2 = Solution().reverseList(head);
        printLinkedList(head2);
    
        deleteLinkedList(head2);
    
        return 0;
    }
    
Copy the code

The results

1 -> 2 -> 3 -> 4 -> 5 -> NULL
5 -> 4 -> 3 -> 2 -> 1 -> NULL
Copy the code

Similar to the topic

leetcode83 Remove Duplicates from Sorted List**

Given an ordered linked list, remove all duplicate elements so that each element is retained only once.

• If 1->1->2, return 1->2
• If 1->1->2->3->3, return 1->2->3

leetcode86 Partition List

Given a linked list and a number x, rearrange the list so that the element less than x comes first; The element greater than or equal to x comes later.

• Such as 1 – > > 4-3 – > 2 – > – > 2, 5 x = 3
• Return 1 – > 2 – > 4 – > 2 – > 3 – > 5

leetcode328 Odd Even Linked List

Given a linked list, rearrange the list so that all nodes with an odd index are placed before those with an even index.

• Such as 1 – > 2 – > 3 – > 4 – > 5 – > NULL
• Return 1 – > 3 – > 5 – > 4 – > 2 – > NULL
• The first node has an index of 1
• Odd-indexed and even-indexed nodes are rearranged in relative order.

leetcode2 Add Two Numbers**

Give two non-empty linked lists representing two non-negative integers. The digits of each integer are stored in reverse order, and the linked list represented by the sum of the two integers is returned.

• 342 + 465 = 807
• If 2->4->3 and 5->6->4 are given, return 7->0->8

Whether there is a leading 0 in the number. (no leading 0 except 0) negative?

leetcode445 Add Two Numbers II**

Give two non-empty linked lists representing two non-negative integers. The bits of each integer are stored in order, and the linked list represented by the sum of the two integers is returned.

• 342 + 465 = 807
• Give 3->4->2 and 4->6->5, and return 8->0->7

Tip * What if you are not allowed to modify the input linked list? * Use secondary data structures

Set up the virtual header of the linked list

Leetcode203. Delete nodes in the linked list

• This logic still applies to removing the last element

• This logic does not apply to deleting the first element

No virtual header code is used

Public: ListNode* removeElements(ListNode* head, int val) {public: ListNode* removeElements(ListNode* head, int val) {while( head ! = NULL && head->val == val ){ ListNode* node = head; head = head->next; delete node; }if( head == NULL )
                return head;
    
            ListNode* cur = head;
            while( cur->next ! = NULL ){if( cur->next->val == val ){
                    ListNode* delNode = cur->next;
                    cur->next = delNode->next;
                    delete delNode;
                    //delNode -> next = NULL;
                }
                else
                    cur = cur->next;
            }
    
            returnhead; }};Copy the code

Virtual header code

Class Solution {public: ListNode* removeElements(ListNode* head, int val) { ListNode* dummyHead = new ListNode(0); dummyHead->next = head; ListNode* cur = dummyHead;while( cur->next ! = NULL ){if( cur->next->val == val ){
                    ListNode* delNode = cur->next;
                    cur->next = delNode->next;
                    delete delNode;
                }
                else
                    cur = cur->next;
            }
    
            ListNode* retNode = dummyHead->next;
            delete dummyHead;
    
            returnretNode; }};Copy the code

Similar problems

leetcode 82. Remove Duplicates from Sorted List II

Given an ordered linked list, delete all duplicate elements.

* such as 1 - > 2 - > 3 - > 3 - > 4 - > 4 - > 5, return 1 - > 2 - > 5 * such as 1-1-1 - > > > 2 - > 3, return 2 - > 3Copy the code

leetcode 21. Merge Two Sorted Lists

Merge Two ordered linked lists

Complex linked list operations

Leetcode 24. Swap nodes in linked lists in pairs

Steps diagram

The core is to create several Pointers that are pre-reserved.

Code implementation

    class Solution {
    public:
        ListNode* swapPairs(ListNode* head) {
    
            ListNode* dummyHead = new ListNode(0);
            dummyHead->next = head;
    
            ListNode* p = dummyHead;
            while( p->next && p->next->next ){
                ListNode* node1 = p->next;
                ListNode* node2 = node1->next;
                ListNode* next = node2->next;
                node2->next = node1;
                node1->next = next;
                p->next = node2;
                p = node1;
            }
    
            ListNode* retHead = dummyHead->next;
            delete dummyHead;
    
            returnretHead; }};Copy the code

Similar to the topic

leetcode 25. Reverse Nodes in k-Group

Given a linked list of k nodes as a group, invert each group of K nodes. K is a positive integer and less than or equal to the length of the list. If the list length is not an integer multiple of k, the rest does not need to be reversed. Such as: 1 – > 2 – > 3 – > 4 – > 5 – > NULL

If k = 2, the result is: 4 - > 2 - > 1 - > 3 - > 5 - > NULL if k = 3, the result is: 3 - > 1 - > 2 - > 4 - > 5 - > NULLCopy the code

leetcode 147. Insertion Sort List

Insert sort for a linked list

leetcode 148. Sort List

Write a sorting algorithm that sorts a linked list in order nlogn time

Merge sort does not use an array index: bottom up.

Modify the linked list node directly

Leetcode237. Delete nodes in a linked list

Train of thought

The assignment method is used to change the value of nodes in special cases to achieve the function we need.

class Solution { public: void deleteNode(ListNode* node) { assert(node ! = NULL && node->next ! = NULL); node->val = node->next->val; ListNode* delNode = node->next; node->next = delNode->next; delete delNode;return; }};Copy the code

Two-pointer technique

leetcode 19. Remove Nth Node From End of List

Pay attention to

• N equals zero or n equals one
• N is not valid, negative or greater than the length of the list.

Solution 1: first go through to calculate the length of the linked list; Go through it again delete the NTH node to the last and go through the list twice. Can we just go through the list once?

Code implementation

/**
 * Definition forsingly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution {public: ListNode* removeNthFromEnd(ListNode* head, int n) {public: ListNode* removeNthFromEnd(ListNode* head, int n) assert(n >= 0); ListNode* dummyNode = new ListNode(0); dummyNode -> next = head; ListNode* p = dummyNode; ListNode* q = dummyNode;for(int i = 0; i < n+1; i++){
            assert(q); 
            q = q -> next;
        }
        
        while(q ! = NULL){ q = q -> next; p = p -> next; } ListNode* delNode = p -> next; p -> next = delNode -> next; delete delNode; ListNode* retNode = dummyNode -> next; delete dummyNode;returnretNode; }};Copy the code

Similar problems

leetcode 61. Rotate List

Given a linked list, rotate the list k bits to the right. Where k is non-negative.

Such as: 1 - > 2 - > 3 - > 4 - > 5 - > NULL, k = 2 first rotation: 5 - > 1 - > 2 - > 3 - > 4 - > NULL second rotation: 4 - > 5 - > 1 - > 2 - > 3 - > NULLCopy the code

leetcode 143. Reorder List

Given a linked list L(0) -> L(1) -> L(2) ->… – > L (n – 1) – > L (n) it into the L (0) – > L (n) – > (1) – > L L (n – 1) – (2) – > > L L (n – 2)… In the form of

Pay attention to

• Linked lists can’t randomly access data. How do you get intermediate elements?
• Double traverse? Traversal?

leetcode234. Palindrome Linked List

Given a linked list, determine if the list is palindromic (looking forward and backward).

Pay attention to

• Can you solve the problem with O(1) space complexity?

---

— — — — — — — — — — — — — — — — — — — — — — — — — gorgeous line — — — — — — — — — — — — — — — — — — — —

After watching the friends can click a like/follow, your support is the biggest encouragement to me.

Personal blog tomato tech small stack

If you want to know more, please follow my wechat official account: Tomato Technology Xiaozhan