*List reversal

Title Description ： Define a function , Enter the head node of a linked list , Invert the linked list and output the head node of the inverted linked list

// Head node definition 
  struct ListNode {
      int val;
      ListNode *next;
      ListNode(int x) : val(x), next(NULL) {}
  };

Ideas ： For linked list inversion , The most common method is to insert and reverse the nodes all the time next 了 , These two methods have two cases respectively , The linked list has head nodes and the linked list has no head nodes . Straight in ： Straight head insertion is to remove the nodes of the original linked list from front to back, and then reconnect to the head node , Because the first inserted node is always behind the linked list , So after re inserting the head , The linked list is inverted .

Method 1 ： Always insert the diagram ( Headless node )：

Code implementation

    ListNode* reverseList(ListNode* head) {
	ListNode* p = head;
	ListNode* s = NULL;
	head = NULL;
	while (p != NULL)
	{
		s = p;
		p = p->next;
		s->next = head;
		head = s;
	}
    return head;
    }

There are head nodes ：

  Code implementation ：

ListNode* Reverse(ListNode* p)
{
	assert(p != NULL);
	if (p == NULL && p->next == NULL)
	{
		return p;
	}
	ListNode* head = (ListNode*)malloc(sizeof(ListNode));
	head->next = NULL;
	while (p != NULL)
	{
		ListNode* s = p; 
		p = p->next;
		s->next = head->next;
		head->next = s;
	}
	p = head->next;
	free(head);
	return p;
}

Method 2 ： Reverse the list of next Domain diagram ( Headless node )：

 

Code implementation ：

   ListNode* reversePrint(ListNode* head) 
    {
        ListNode *p=NULL;
        ListNode *q=head->next;
        ListNode *r=head->next;
        head->next=NULL;
        while(r->next!=NULL)
        {
            q->next=p;
            p=q;
            q=r;
            r=r->next;
        }
        return head;
    }

Header node code implementation ：

   ListNode* reversePrint(ListNode* head) 
    {
        ListNode *p=NULL;
        ListNode *q=head->next->next;
        ListNode *r=head->next->next;
        head->next->next=NULL;
        head->next=NULL;
        while(r->next!=NULL)
        {
            q->next=p;
            p=q;
            q=r;
            r=r->next;
        }
        head->next=q;
        return head->next;
    }

Method 3 ： Recursive inversion ：

ListNode* RevList(ListNode* pre, ListNode* p)
{
	ListNode* tail = NULL;
	if (p != NULL)
	{
		tail = RevList(p, p->next);
		p->next = pre;
	}
	else
	{
		tail = pre;
	}
	return tail;
}