LeetCode206. Reverse linked list [double pointer and recursion]

LeetCode206. Reverse a linked list

1. subject

2. Ideas

1. My initial idea was to move the last node forward in turn , Later, I found two difficulties . One is that the one-way linked list cannot access the precursor nodes of the known nodes , Made some mistakes . such as ：
（1） LinkNode*q; q->next = p; //q It doesn't point to p The precursor of
（2）LinkNode *q = dummyHead; q->next = p; // This will become dummyHead Of next Turn into p The linked list is wrongly arranged ！
Second, if you need to access the precursor node , Every time I need to traverse , Time complexity is too high . Sum up , I gave up the idea .
2. Double pointer application . Set one front node and one rear node to move backward in sequence . Make the pointer of the following node point to the node in front of it .
3. recursive .
Let's implement it separately .

3. Code implementation

（1） Double pointer application

The basic idea of double pointer ：

1. My initial idea is to count the length of the linked list , The special judgment length is 0/1 The situation of , Finally, use double pointers . This is a little complicated
2. Remember to use tmp After the node is saved, the node behind the pointer , Or you lose it
The main idea is the figure above ：（1） Save node （2） Pointer reversal （3） Pointer backward

First post my initial code , Very complicated , There are many redundant steps …

class Solution {
    
public:
    ListNode* reverseList(ListNode* head) {
    
	ListNode* dummyHead = new ListNode(1);// Sentinel node   Consider that the header node is empty  
	if(head!= NULL) dummyHead->next = head; 
	ListNode* p = dummyHead;
	int size = 0;// initialization ！
	while(p->next != NULL)
	{
    
		p = p->next;
		size++;// Chain length  
	}
	// It is specially judged that the empty linked list and length are 1 The situation of 
	if(size == 0) return nullptr;
	else if(size == 1) return head;
	else{
    
		ListNode *m = dummyHead->next;
		ListNode *n = dummyHead->next->next;
        ListNode *tmp;
		while(n != NULL)
		{
    // Save node 
			tmp = n->next;
		// reverse 
            n->next = m;
            m = n;
        // Move backward 
            n = tmp;
		}
        dummyHead->next->next = nullptr;// This sentence must have a meaning 
        delete dummyHead;
		return m;
		}
	}
};

Compared with the big guy's code, there are two biggest shortcomings ：

1. There is no need to use sentinel nodes , Too much , And easy to lose dummyHead->next->next = nullptr; This step .
2. Recently, I have developed the awareness of special judgment , The empty linked list and nodes will be 1 Think about the linked list , Very happy . But special judgment is not necessary , Can be more streamlined ！

The streamlined code ：

class Solution {
    
public:
    ListNode* reverseList(ListNode* head) {
    
	ListNode* tmp;
	ListNode* m = NULL;
	ListNode* n = head;
	while(n != NULL)
	{
    
	// Save node 
		tmp = n->next;
	// reverse 
		n->next = m;
	// Move backward 
		m = n;
		n = tmp;
	}// There is no need to make a special judgment on the head node , The first step is to set NULL 了 
	return m;
	}
};

（2） Recursive method

The same idea as double pointer

ListNode* reverse(ListNode*m,ListNode* n){
    
	if(n == NULL) return m;// Recursive export  
	// Storage point  
	ListNode* tmp = n->next;
	// In exchange for 
	n->next = m;
	// Move backward   Here I stuck for a while   But it's actually the same as the double pointer idea 
	//m = n;
	//n = tmp; 
	return reverse(n,tmp);
}

ListNode* reverseList(ListNode* head) {
    
	// Is the initialization of double pointers  
	//ListNode* m = NULL; ListNode* n = head;
	return reverse(NULL,head);
}