L2.【LeetCode笔记】反转链表

1.题目

2.自解

代码

为了练习讲过的头插函数,另外开辟空间,使用遍历算法

struct ListNode* reverseList(struct ListNode* head) 
{
    typedef struct c_ListNode
    {
        int c_val;
        struct ListNode* c_next;
    }c_L;
    c_L* c_head=NULL;
    struct ListNode* cur=head;
    while (cur)
    {
        int x=cur->val;
        {
            c_L* newnode = (c_L*)malloc(sizeof(c_L));

	        newnode->c_val = x;
	        newnode->c_next = NULL;
	        
            newnode->c_next = c_head;
	        c_head = newnode;
        }
        cur=cur->next;
    }

    return c_head;
}

提交结果

LeetCode上测算代码的时间复杂度和空间复杂度均为

3.代码分析 

1.反转链表显然使用头插,但不能在原来链表的基础上头插,数据会被覆盖,因此本代码创建了初始化了一个新链表struct c_ListNode(为copy_ListNode的缩写,复制ListNode的结构),成员变量为c_val(copy_val的缩写)和c_next(c_next的缩写)

    typedef struct c_ListNode
    {
        int c_val;
        struct ListNode* c_next;
    }c_L;

2.c_L链表的头指针初始化为NULL，cur为ListNode的head头节点的拷贝

c_L* c_head=NULL;
struct ListNode* cur=head;

3.while (cur)未到NULL则继续遍历ListNode链表,x取得当前cur指向的节点的val,c_L* newnode = (c_L*)malloc(sizeof(c_L));为新节点newnode开辟空间,newnode->c_val = x;和newnode->c_next = NULL;初始化化新节点

    while (cur)
    {
        int x=cur->val;
        {
            c_L* newnode = (c_L*)malloc(sizeof(c_L));

	        newnode->c_val = x;
	        newnode->c_next = NULL;

	        newnode->c_next = c_head;
	        c_head = newnode;
        }
        cur=cur->next;
    }

4.LeetCode官方解法

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* reverseList(struct ListNode* head) 
{
    //双指针
    struct ListNode* prev = NULL;
    struct ListNode* curr = head;

    while (curr) 
    {
        struct ListNode* next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

不用单独判断空链表 

时间复杂度为

思想:只需要反过来指即可

执行步骤

1.保存下一节点的指针

 struct ListNode* next = curr->next;

2.拆除原先的指针,设置节点的新指针

curr->next = prev;

3.移动快慢指针

        prev = curr;
        curr = next;

5.其他解法

 第一次遍历链表的所有节点,将所有的节点val存入数组中,在将数组中的数据逆向复制至节点的val(低速解法)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* reverseList(struct ListNode* head) 
{
    if (head==NULL)
    return NULL;

    struct ListNode* cur=head;
    int arr[5000]={0};
    int i=0;
    while(cur)
    {
        arr[i]=cur->val;
        i++;
        cur=cur->next;
    }
    i--;
    cur=head;
    while(i>=0&&cur!=NULL)
    {
        cur->val=arr[i];
        i--;
        cur=cur->next;
    }
    return head;
}

注意

1.在while(cur)和while(i>=0&&cur!=NULL)之间有一个i--;这一步非常重要,不可缺失,否则导致反转链表的第一个节点的val的值为0

2.此代码执行后占用极多的内存空间(int arr[5000]占5000*4=20000byte,约为19MB)，不建议使用