[Leetcode]链表反转

力扣链接

方法一:

经典的双指针问题,这里为了方便采用三指针

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* reverseList(struct ListNode* head)
{


    struct ListNode* n1,*n2,*n3;
    n1 = NULL;
    n2 = head;
    n3 = n2->next;
    if(head == NULL)
    {
        return NULL;
    }
    while(n2)
    {
        //翻转
        n2->next = n1;
        //迭代
        n1 = n2;
        n2 = n3;
        n3 = n3->next ;


    }
     
    return n1;
   



}

如图第28行出现了null pointer (空指针),所以n3可能为空,只需判断n3是否为空,当然有时报错不一定准确,需要进一步分析.

改进后代码:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */



struct ListNode* reverseList(struct ListNode* head)
{


    struct ListNode* n1,*n2,*n3;
    n1 = NULL;
    n2 = head;
    n3 = n2->next;
    if(head == NULL)
    {
        return NULL;
    }
    while(n2)
    {
        //翻转
        n2->next = n1;
        //迭代
        n1 = n2;
        n2 = n3;
        if(n3)
        {
            n3 = n3->next ;
        }
    }
     
    return n1;
   



}

这里的报错就不准确了,最后输入的测试用例给出了出错的原因-----链表可能为空,同样的只需判断就行:

最终代码:

/**
 * 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* n1,*n2,*n3;
    n1 = NULL;
    n2 = head;
    n3 = n2->next;
    if(head == NULL)
    {
        return NULL;
    }
    while(n2)
    {
        //翻转
        n2->next = n1;
        //迭代
        n1 = n2;
        n2 = n3;
        if(n3)
        {
            n3 = n3->next ;
        }
    }
     
    return n1;
   



}

方法二:

取节点头插到新链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */



struct ListNode* reverseList(struct ListNode* head)
{
    struct ListNode* cur,*newHead;
    cur = head;
    newHead = NULL;
    while(cur)
    {
        struct ListNode* next = cur->next;
       cur->next = newHead;
       newHead = cur;
       cur = next;
    } 
    return newHead;
}