反转链表的四种方法_反转链表c语言

力扣206 反转链表
结构体定义

struct ListNode {
      int val;
      struct ListNode *next;
  };
1
2
3
4

一 . 新建链表法

定义一个头节点，遍历链表，运用头插法将每个节点通过头节点插入道新建链表中。

总结：
1个头结点，2个指针（包含一个临时保存节点的pNex）

struct ListNode* reverseList(struct ListNode* head){
//定义一个头节点
    struct ListNode* Newhead;
    Newhead = (struct ListNode*)malloc(sizeof( struct ListNode));
    struct ListNode *pcur = head, *pnex, *L;
    L = Newhead;
    L->next = NULL;
    while(pcur) {
        pnex = pcur->next;
        pcur->next = L->next;
        L->next = pcur;
        pcur = pnex;
    }
    return Newhead->next;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

二 . 三个指针的方法

从前往后遍历链表，定义三个指针分别指向三个结点，反转前两个结点，即让第二个结点指向第一个结点。然后依次往后移动指针，直到第二个结点为空结束，再处理链表头尾即可。

代码：

//三个指针
struct ListNode* reverseList(struct ListNode* head){
    struct ListNode *p = NULL, *q = head, *nexttmp = NULL;
    while(q) {
        nexttmp = q->next;
        q->next = p;
        p = q;
        q = nexttmp;
    }
    return p;
}
1
2
3
4
5
6
7
8
9
10
11

三.递归法

调用子链，递归实现

代码：

struct ListNode* reverseList(struct ListNode* head){

    if( !head || !head->next) return head;
    struct ListNode* Newhead = reverseList(head->next);
    head->next->next = head;
    head->next = NULL;
    return Newhead;
}
1
2
3
4
5
6
7
8

四.就地反转

定义一个头节点，将当前链表的下一个节点插入到头节点后面，当前节点再依次向后移动。就地反转
Newhead->1->2->3->4->5的就地反转过程：
Newhead->2->1->3->4->5
Newhead->3->2->1->4->5
Newhead->4>-3->2->1->5
Newhead->5->4->3->2->1

图片上用L代替Newhead。
代码：

struct ListNode* reverseList(struct ListNode* head){
//定义一个头节点
    if(head == NULL) return head;
    struct ListNode* Newhead;
    Newhead = (struct ListNode*)malloc(sizeof( struct ListNode));
    struct ListNode* pre = head; 
    struct ListNode* pur;
    Newhead->next = head;
    pur = head->next;
    while(pur) {
        pre->next = pur->next;
        pur->next = Newhead->next;
        Newhead->next = pur;
        pur = pre->next;
    }
    return Newhead->next;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

总结

方法一和方法四都定义了一个头节点，运用头节点，来完成操作
方法二利用三个指针，操作简单，易懂
方法三运用递归，代码简便，但是理解有难度，要好好想一下。