比翼网站建设专业seo培训学校

 题目描述：

给出一个链表的头节点，将其反转，并返回新的头节点

思路1：反转地址

将每个节点里的地址由指向下一个节点变为指向前一个节点

定义三个结构体指针n1,n2,n3,n1表示改后指针的地址，n2表示要修改结构体里next的节点，n3用来存储下一个节点，如果没有n3，修改n2的next之后，就找不到下一个节点了，迭代就不能实现。

注意：链表可能为空链表，要讨论链表为空链表的情况 

n3为空时就不能指向下一个节点，会非法访问地址，因此还要判断n3是否为空

struct ListNode* reverseList(struct ListNode* head)
{//当链表为空时，返回NULLif (head == NULL)return NULL;else{//初始条件struct ListNode* n1 = NULL;struct ListNode* n2 = head;struct ListNode* n3 = n2->next;//结束条件while (n2){n2->next = n1;n1 = n2;n2 = n3;//n3不能为空if (n3)n3 = n3->next;}return n2;}
}

思路2：头插法

取原链表的节点，头插到新链表

注意：要记录头插到新链表的下一个节点next，同时记录当时插入的节点newhead

struct ListNode* reverseList(struct ListNode* head)
{struct ListNode* newhead = NULL;struct ListNode* cur = head;while (cur){//记录下一个节点的位置struct ListNode* next = cur->next;cur->next = newhead;//记录插入新链表的节点newhead = cur;cur = next;//寻找原链表的下一个节点，继续插入}return newhead;}