Sword finger offer|: linked list (simple)

List of articles

1. 【 Stack and queue 】

---

---

The finger of the sword Offer 06. Print linked list from end to end

Original link ： Print linked list from end to end

Enter the head node of a linked list , Return the value of each node from the end to the end （ Return with array ）.

Answer key ：
Use the virtual head node to accept the inverted linked list , Then iterate through the list , Tail into return array .

class Solution {
    
public:
    vector<int> reversePrint(ListNode* head) {
    
        ListNode* dummy = new ListNode();
        dummy = ReverseList(head);

        vector<int> ans;
        while (dummy != nullptr) {
    
            ans.emplace_back(dummy->val);
            dummy = dummy->next;
        }

        return ans;
    }
	
	//  Reverse of linked list 
    ListNode* ReverseList(ListNode* head) {
    
        ListNode* prev = nullptr;
        ListNode* curr = head;
        while (curr != nullptr) {
    
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
};

The finger of the sword Offer 35. Replication of complex linked list

Original link ： Replication of complex linked list

Please implement copyRandomList function , Copy a complex list . In complex linked list , Each node has one next The pointer points to the next node , One more random The pointer points to any node in the list or null.

Answer key ：

We first split each node in the linked list into two connected nodes , For example, for a linked list A→B→C, We can split it into A→A′→B→B′→C→C’. For any original node S, Its node copies S′ That is, its successor node .

such , We can find each copy node directly S′ The random pointer to the node that should be pointed to , Is its original node S The random pointer to the node T Successor node T′. Note that the random pointer of the original node may be null , We need to judge this situation in particular .

When we complete the assignment of the random pointer of the copy node , We only need to split the linked list according to the types of the original node and the copy node , You only need to traverse it once . Also note that the successor node of the last copy node is empty , We need to judge this situation in particular .

class Solution {
    
public:
    Node* copyRandomList(Node* head) {
    
        if (head == nullptr) {
    
            return nullptr;
        }

        for (Node* node = head; node != nullptr; node = node->next->next) {
    
            Node* nodeNew = new Node(node->val);
            nodeNew->next = node->next;
            node->next = nodeNew;
        }
        
        for (Node* node = head; node != nullptr; node = node->next->next) {
    
            Node* nodeNew = node->next;
            nodeNew->random = (node->random != nullptr) ? node->random->next : nullptr;
        }

        Node* headNew = head->next;
        for (Node* node = head; node != nullptr; node = node->next) {
    
            Node* nodeNew = node->next;
            node->next = node->next->next;
            nodeNew->next = (nodeNew->next != nullptr) ? nodeNew->next->next : nullptr;
        }
        return headNew;
    }
};