反转链表

题目:

给定一个单链表的头结点pHead,长度为n,反转该链表后,返回新链表的表头。
 
数据范围: n\leq1000n≤1000
要求:空间复杂度 O(1)O(1) ,时间复杂度 O(n)O(n) 。
 
如当输入链表{1,2,3}时,
经反转后,原链表变为{3,2,1},所以对应的输出为{3,2,1}。

题目的意思很好理解,就是按照相反的顺序输出一个链表。

这道题有两种思路,第一种很简单,就是先便利一遍链表,并把数存一下,然后再新建一个链表,将对应的数插进去,再返回新建链表的头指针即可。

第二种思路是在原链表的基础上,改变链表的指向。

首先看第一种方法:

struct ListNode* ReverseList(struct ListNode* pHead ) {
    // write code here
    int n=0;
    int a[1000];
    struct ListNode* Head;
    Head=(struct ListNode*)malloc(sizeof(struct ListNode));
    while(pHead!=NULL){
        a[n]=pHead->val;
        ++n;
        pHead=pHead->next;   
    }
    struct ListNode *end,*node;
    end=Head;
    for(int i=0;i<n;++i){
        node=(struct ListNode*)malloc(sizeof(struct ListNode));
        node->val=a[n-1-i];
        end->next=node;
        end=node;
    }
    end->next=NULL;
    return Head->next;
}

 C的代码附在上面了,这个还是比较好理解的哈!

官方的题解上面给的C++写法跟这个差不多,不过它用的是vector,差不多的意思。

 

第二种方法:

先看代码吧:

struct ListNode* ReverseList(struct ListNode* pHead ) {
    // write code here
    
    struct ListNode* node,* end;
    end=NULL; //待反转的结点
    node=pHead; //作为反转后的头结点
    while(node->next){//如果下一跳是null,说明反转结束了
        pHead=node->next; //首先保证待反转的结点和后面的结点“联系不能断”
        node->next=end; //反转
        end=node; //往后传递待反转的结点
        node=pHead; 
    }
//循环结束后,node结点指向的是反向结点的头。但是经过上述循环后,反向的第一个结点和第二个结点之间并未建立联系,所以有下面的操作 pHead=node; pHead->next=end; return pHead; }

 

------------------------------------------------------------

上述第二种方法的代码可以过样例,但是提交则显示段错误,后经检查,发现如果输入的是一个空链表的话,会出现找不到指针的问题,所以更改后的代码如下下:

struct ListNode* ReverseList(struct ListNode* pHead ) {
    // write code here
    struct ListNode* node,* end;
    end=NULL;
    node=pHead;
    while(node){
        pHead=node->next;
        node->next=end;
        end=node;
        node=pHead;
    } 
    return end;
}

两种方法都很好理解,这一题也是一道基础题。

 (点点关注和赞吧各位大佬)

上一篇:[C语言]顺序表、链表的简单实现


下一篇:链表中倒数最后k个结点