链表逆序

定义ListNode节点结构体

struct ListNode {
     int val;
     ListNode *next;
     ListNode(int x) : val(x),next(NULL)
}

例题: 链表链接

int main(){
    ListNode a(10);
    ListNode b(20);
    ListNode c(30);
    ListNode d(40);
    ListNode e(50);

    a.next = & b;
    b.next = & c;
    c.next = & d;
    d.next = & e;
    ListNode *head = & a;
    while(head){
        print("%d %p %P\n,head->val, head,head->next");
        head = head->next
    }
    return 0;
    
}

LeetCode 206. Reverse Linked List

Eg1.链表逆序

一只链表头节点,指针head,将链表逆序。(不可申请额外空间)

链表数据结构

struct  ListNode{
int val;
ListNode  *next;
ListNode(int x) : val(x),next(NULL){}
};

打印head指针指向的链表

void print_list(ListNode * head,const char *List_name){
    printf("%S :",List_name);
    if(!head){
        printf("NULL\n");
        return;
    }
    while(head){
        printf("%d",head->val);
        head = head->next;
    }
    printf("\n");
}

1.构造5个节点a,b,c,d,e,并对它们进行初始化; 2.将a,b,c,d,e,5个节点连接在一起

int main(){
    ListNode a(1);
    ListNode b(2);
    ListNode c(3);
    ListNode d(4);
    ListNode e(5);
    a.next = &b;
    b.next = &c;
    c.next = &d;
    d.next = &e;

    ListNode *head =&a;
    ListNode *new_head = NULL;
    LIstNode *next = NULL;
    print_list(head,"old");
    print_list(new_head,"new");
    return 0;


}

1、就地逆置法

1.备份head->next 2.修改head->next 3.移动head与new_head

class Solution{
public :
    ListNode *reverseList(ListNode * head){
    ListNode *new_head =NULL;//指向新链表头节点的指针
    while(head){
     ListNode * next = head->next;//备份head->next
     head->next = new_head; //更新head->next
     new_head = head_next; //移动new_head
     head = next;//遍历链表
     
}
return new_head;//返回新链表头节点
}
}

2、头插法

设置一个临时头节点temp_head,利用head指针遍历链表,每遍历一个节点即将该节点插入到temp_head后

1.备份next = head->next; 2.修改head->next 3.temp_head.next 4.移动head

class Solution{
public:
    ListNode * reverseList(ListNode * head){
    ListNode temp_head(0);
    while(head){
    ListNode *next = head->next;
    head->next = temp_head.next;
    temp_head.next = head;
    head =next;
}
    return temp_head.next;
}
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 链表划分

    LeetCode 86.Partition List 已知链表头节点指针head与数值X,将所有小于x的节点放在大于或等于x的节点前,且保持这些节点的原来的相...

    小飞侠xp
  • 链表求环

    LeetCode 141. Linked List Cycle 142.Linked List Cycle II

    小飞侠xp
  • 链表中间段逆序

    LeetCode 92. Reverse Linked List II 已知链表头节点指针head,将链表从位置m到n逆序。(不申请额外空间)

    小飞侠xp
  • Leetcode 24. Swap Nodes in Pairs

    版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.csdn....

    Tyan
  • 【leetcode刷题】T104-翻转链表

    木又AI帮
  • Leetcode 142 Linked List Cycle II

    Given a linked list, return the node where the cycle begins. If there is no cyc...

    triplebee
  • Leetcode 24 Swap Nodes in Pairs

    Given a linked list, swap every two adjacent nodes and return its head. For ex...

    triplebee
  • LeetCode 24 Swap Nodes in Pairs

    ShenduCC
  • LeetCode 每日一题206: 反转链表

    按照题目的要求, 今天给出两个思路, 个人觉得迭代会比较容易思考出来, 先给出迭代的思路.

    benny
  • LeetCode 每日一题206: 反转链表

    按照题目的要求, 今天给出两个思路, 个人觉得迭代会比较容易思考出来, 先给出迭代的思路.

    benny

扫码关注云+社区

领取腾讯云代金券