【算法题】3.反转链表

设计一个算法,将链表中所有节点的链接⽅向"原地旋转",即要求仅利⽤原表的存储空间。

题目大意：

反转链表，要求不使用临时空间。

输入：

0->2->4->6->8->10

题目

设计一个算法,将链表中所有节点的链接⽅向"原地旋转",即要求仅利⽤原表的存储空间。

题目大意：

反转链表，要求不使用临时空间。

输入：

0->2->4->6->8->10

输出：

10->8->6->4->2->0

解析：

使用迭代，链表头插法。

时间复杂度：

空间复杂度：

代码

void reverseLists(LinkList *L){
  
    if (*L == NULL)
    {    
     return ;
    }
    ListNode *p = (*L)->next; //0
    
    ListNode *q;

    (*L)->next = NULL;
    
    while(p != NULL){
         q= p->next;//2 4 6 8 10...
         p->next = (*L)->next;//0->NULL,2->0...
         (*L)->next = p;//L->0,L->2...
         p = q;//2 4 6 8...
    }
}

输出：

10->8->6->4->2->0

解析：

使用迭代，链表头插法。

时间复杂度：O(n)

空间复杂度：O(1)

代码

void reverseLists(LinkList *L){
  
    if (*L == NULL)
    {    
     return ;
    }
    ListNode *p = (*L)->next; //0
    
    ListNode *q;

    (*L)->next = NULL;
    
    while(p != NULL){
         q= p->next;//2 4 6 8 10...
         p->next = (*L)->next;//0->NULL,2->0...
         (*L)->next = p;//L->0,L->2...
         p = q;//2 4 6 8...
    }
}