Reverse Linked List

Define the linked list node as:

The requirement is to reverse a singly linked list with a head node List head.

Analysis:

1). If the linked list is empty or contains only one element, return directly;

2). Set up two adjacent pointers, p and q. The node pointed to by p will become the successor of the node pointed to by q;

3). Repeat step 2) until q is null.

4). Adjust the head and tail of the linked list.

Example: Taking A->B->C->D as an example for reversal, the diagram is as follows:

The implementation and test code are as follows:

[cpp:nogutter] view plain copy

#include <stdio.h>
#include <stdlib.h>
typedef struct tagListNode{
int data;
struct tagListNode* next;
}ListNode, *List;
void PrintList(List head);
List ReverseList(List head);
int main()
{
//Allocate head node for the linked list
ListNode *head;
head = (ListNode*)malloc(sizeof(ListNode));
head->next = NULL;
head->data = -1;
//Add [1,10] to the linked list
int i;
ListNode *p, *q;
p = head;
for(int i = 1; i <= 10; i++)
{
q = (ListNode *)malloc(sizeof(ListNode));
q->data = i;
q->next = NULL;
p->next = q;
p = q;
}
PrintList(head); /* Output original linked list */
head = ReverseList(head); /* Reverse linked list */
PrintList(head); /* Output reversed linked list */
return 0;
}
List ReverseList(List head)
{
if(head->next == NULL || head->next->next == NULL)
{
return head; /* If the linked list is empty or has only one element, return directly */
}
ListNode *t = NULL,
*p = head->next,
*q = head->next->next;
while(q != NULL)
{
t = q->next;
q->next = p;
p = q;
q = t;
}
/* At this point, q points to the last element of the original list, which is also the head element of the reversed list */
head->next->next = NULL; /* Set the linked list tail */
head->next = p; /* Adjust the linked list head */
return head;
}
void PrintList(List head)
{
ListNode* p = head->next;
while(p != NULL)
{
printf("%d ", p->data);
p = p->next;
}
printf("/n");
}