| 【数据结构】单链表逆置：头插法图解 | 您所在的位置：网站首页 › c语言图解 › 【数据结构】单链表逆置：头插法图解 |
【数据结构】单链表逆置：头插法图解
|
利用头插法能重新建立带头节点的新链表
下面简单介绍一下，算法思想结合图示看 算法思想：逆置链表初始为空，表中节点从原链表中依次“删除”，再逐个插入逆置链表的表头（即“头插”到逆置链表中），使它成为逆置链表的“新”的第一个结点，如此循环，直至原链表为空。 LNode *Inverse(LNode *L) { LNode *p, *q; p = L->next; L->next = NULL; while (p != NULL) { q = p; p = p->next; q->next = L->next; L->next = q; } return L; }接下来，进行图解： 刚开始是这样
进入循环，分别用q和p记录第一个和第二个节点 进入第二轮循环，这是发生重大变化的关键时期 这张图调整一下 直到链表为空 这篇文章已经一年半了，还是源源不断有不同的评论，去探讨相关的问题，其实图解不一定清晰。下面用更简明的方式给大家说一下什么情况。 这里采用Java的写法，C一定也能看懂。 我首先创建三个节点，一个是当前节点cur、一个是cur上一个节点pre。另外就是tmp。 每次循环，我用tmp记录cur下一个节点，接着将cur的next指针指向上一个节点pre。这个时候就完成了一次反转操作。 接着将pre和cur的记录往后移动一次，重复上面的操作。 直至达到链表结尾。 class Solution { public ListNode reverseList(ListNode head) { //申请节点，pre和 cur，pre指向null ListNode pre = null; ListNode cur = head; ListNode tmp = null; while(cur!=null) { //记录当前节点的下一个节点 tmp = cur.next; //然后将当前节点指向pre cur.next = pre; //pre和cur节点都前进一位 pre = cur; cur = tmp; } return pre; } }
|
’循环前的操作
【本文地址】
公司简介
联系我们