给你单链表的头节点 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
注意这是个单链表,所以不能从后往前遍历来达成反转操作。 思路一:创建新链表 进行头插
但这里可以使用另外一种方法。
也就是下方的思路二:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {
// 思路二:创建三个指针,分别记录前驱结点、当前结点、后继结点。
//只改变原链表指针指向,而不改变元素的位置(基于链表存储的性质)
if (head == NULL) {
return head;
}
ListNode *n1, *n2, *n3;
n1 = NULL, n2 = head, n3 = head->next;
// 遍历原链表,修改结点指针指向
while (n2) {
// 反转n2指向
n2->next = n1;
// 修改三个指针位置
n1 = n2;
n2 = n3;
if (n3)
n3 = n3->next;
}
return n1;
}