题目描述:
给定单链表的头节点 head ,请反转链表,并返回反转后的链表的头节点。
示例 1:
输入:head = [1,2,3,4,5]
输出:[5,4,3,2,1]
示例 2:
输入:head = [1,2]
输出:[2,1]
示例 3:
输入:head = []
输出:[]
提示:
链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000
题解:
解题思路1:
遍历两遍链表,第一次把所有值取出来,第二次给链表重新赋值(这种解法比较繁琐)
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseList(struct ListNode* head){
int num[5000] = {0};
int length = 0;
struct ListNode* cont = head;
/*
**空指针情况返回空
*/
if(head == NULL)
return NULL;
/*
**第一次遍历,取值
*/
while(cont){
num[length] = cont->val;
length++;
cont = cont->next;
}
cont = head;
head->val = num[length-1];
/*
**第二次遍历,赋值
*/
while(cont){
cont->val = num[length-1];
length--;
cont = cont->next;
}
return head;
}
解题思路2: 递归
如果第1 个节点后面的都已经反转了,现在只需要处理第 1 个和第二个节点即可,通过head->next->next = head可实现。要解决的就是如何将后面的都反转好? 通过递归:reverseList(head->next) 实现,同时要设置一个表头指向排列好后的链表的头结点。
拿[1,2,3,4,5]举例,经过第一步:
1 -> 2 <- 3 <- 4 <- 5
此时head就是 1 所在的节点, newHead 就是 5 所在的节点
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseList(struct ListNode* head) {
if (head == NULL || head->next == NULL) {
return head;
}
/*
**第一步将第1个节点之后的都已经排列好
**1 -> 2 <- 3 <-...<- n
*/
struct ListNode* newHead = reverseList(head->next);
/*
**第二步处理第一个和第二个节点,并将第一个节点指向NULL
*/
head->next->next = head;
head->next = NULL;
return newHead;
}
解题思路3: 迭代
就是用三个指针(bwd curr fwd)去遍历一遍链表
bwd 从 NULL 开始,curr 从 head 开始 ,fwd 从 curr->next 开始 直到 bwd 到了最后一个节点结束,最后返回 bwd 即可,代码就不放了。
题目链接:https://leetcode-cn.com/problems/reverse-linked-list/