初阶数据结构习题【6】（3顺序表和链表）——206.反转链表

1. 题目描述

力扣在线OJ—— 206. 反转链表 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1： 输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]

示例2 输入：head = [1,2] 输出：[2,1]

示例3 输入：head = [] 输出：[]

2. 思路

思路1

思路2 取原节点到新链表，不创建新链表，保存下一个节点，完成头插。然后继续下一个

3. 代码实现

思路1代码实现

struct ListNode* reverseList(struct ListNode* head) { if(head == NULL) { return NULL; } struct ListNode* n1,*n2,*n3; n1 = NULL; n2 = head; n3 = n2->next; while(n2) { //反转 n2->next = n1; //下一步迭代 n1 = n2; n2 = n3; if(n3) { n3 = n3->next; } } return n1; }

思路2代码实现

struct ListNode* reverseList(struct ListNode* head) { if (head == NULL) { return NULL; } struct ListNode *cur, *newhead; cur = head; newhead = NULL; while (cur) { struct ListNode* next = cur->next; // 头插 cur->next = newhead; newhead = cur; cur = next; } return newhead; }