206. 反转链表_算法设计递归方法逆置带头结点的单链表

第一次尝试

  反转一个单链表。链表为无头结点、单向、不循环。（由于涉及到结构体，所以写不了完整的测试代码，下面展示的代码为 LeetCode 中写的代码）(LeetCode链接)

• 本题我写了三种解题方法
• 三种方法之外的方法：动态申请能装下链表数据的空间，然后将链表数据存放到数组中，在数组中将数据逆转，再存放到链表中，不过这种方法太麻烦了，浪费时间空间，不推荐
• 方法一：头插法，再创建一个链表 _head，然后从头遍历原链表 head，再将 head 中的数据以头插法插入到 _head 链表中，这样就完成了链表的逆转
• 方法二：三指针法，前提是至少有两个数据，设置三个结构体指针 p1、p2、p3，一开始 p1指向头结点，p2 指向第二个节点，p3 指向 p2 -> next，此时对于我们来说，需要修改指向的是 p2，p1 是保留的上一个节点，p3 是保留的下一个数据；在循环中，先判断 p2 是否为空，不为空就让 p3 = p2 -> next，然后修改 p2 指向为 p1，更新 p1、p2 指向相对位置的下一个节点；
• 方法三：递归法，假设链表为：n1​ →…→ nk−1​ → nk​ → nk+1 ​→…→ nm ​→∅，现在需要修改 nk + 1 的指向，我们可以不用管 nk + 1 后面的指向，假设他们已经逆转了，如 n1​ →…→ nk−1 ​→ nk​ → nk+1 ​←…← nm​；
      此时我们只需将 nk + 1 的指向为 nk，所以在进行递归时，需要先保留前一个节点 nk，然后调用递归，等递归 return 之后，修改 nk+1 -> next = nk；
      递归的结束条件就是当前节点的 next 指向为空，就返回当前节点，注意，这个节点就将是逆置之后链表的头结点，需要注意的是，等递归完成之后，需要将 head -> next = NULL，否则链表将无法结束；

//递归的函数
struct ListNode* func(struct ListNode* node){
    if(node->next == NULL){
        return node;//这里返回的节点就是最终逆置好了的链表的头结点
    }
    //保留当前节点
    struct ListNode* cur = node;
    node = node->next;
    struct ListNode* ret = func(node);
    node->next = cur;
    return ret;
}

struct ListNode* reverseList(struct ListNode* head){
    //递归的方法
    if(head == NULL||head->next == NULL){
        return head;
    }
    struct ListNode* ret = func(head);
    head->next = NULL;
    return ret;

    //头插法
    if(head == NULL||head->next ==NULL){
        return head;
    }
    //重新创建一个头结点，用来头插入数据
    struct ListNode list;
    list.next = NULL;
    struct ListNode* node = head;
    while(node){
        struct ListNode* next = node->next;
        node->next = list.next;
        list.next = node;
        node = next;
    }
    return list.next;

    //三指针法
    if(head == NULL||head->next ==NULL){
        return head;
    }
    struct ListNode* p1 = head;
    struct ListNode* p2 = p1->next;
    struct ListNode* p3 = p2->next;
    //将原来的头结点指向NULL，就可将其作为尾结点
    p1->next = NULL;
    while(p2){
        //更新指针
        p3 = p2->next;
        p2->next = p1;
        p1 = p2;
        p2 = p3;
    }
    return p1;
}
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56

博客园发表于 2020-12-10 16:11