数据结构--链表题五--反转链表（leetcode-剑指 Offer II 024）_给定单链表头结点,反转链表,并返回反转后的头结点

题目描述：
给定单链表的头节点 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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

解题思路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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

解题思路3： 迭代
就是用三个指针（bwd curr fwd）去遍历一遍链表
bwd 从 NULL 开始，curr 从 head 开始 ，fwd 从 curr->next 开始 直到 bwd 到了最后一个节点结束，最后返回 bwd 即可，代码就不放了。

题目链接：https://leetcode-cn.com/problems/reverse-linked-list/