欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

对链表进行插入排序,巧用虚拟头节点

程序员文章站 2022-03-23 22:14:30
147. 对链表进行插入排序问题描述:传送门思路:1、虚拟头结点dummyHead的运用因为是模拟插入排序的过程,通过画图,可以发现有三次改变节点指针的操作。举个例子:输入端输入4—2—1—3—NULL①因为本题例子很多,要写判断。如果头结点为空,返回空.②而如果head节点不为空,定义cur节点,接收head结点的头结点值;pre节点接收dummyHead节点的值。 if(head==NULL) return head; ListNode*...

147. 对链表进行插入排序

问题描述:传送门对链表进行插入排序,巧用虚拟头节点

思路:

1、虚拟头结点dummyHead的运用
因为是模拟插入排序的过程,
通过画图,可以发现有三次改变节点指针的操作。
举个例子:
输入端输入4—2—1—3—NULL
①因为本题例子很多,要写判断。如果头结点为空,返回空.
②而如果head节点不为空,定义cur节点,接收head结点的头结点值;pre节点接收dummyHead节点的值。

           if(head==NULL)  return head;
            ListNode* dummyHead = new ListNode(0);//定义一个虚拟头结点,并设置为0
            ListNode* cur = head;//接收head节点的值
            ListNode* pre = dummyHead;//接收dummyHead节点的值

首先读入4;
这个时候没法比较pre->next节点与cur节点的值大小,所以不执行while循环。

  while(cur !=NULL){
                while(pre->next !=NULL && pre->next->val < cur->val)
                {
                    pre=pre->next;
                }
            }

对链表进行插入排序,巧用虚拟头节点

所以,执行五步骤法。
步骤一:只能先定义节点Xin保存cur->next节点的值,即保存2
步骤二:cur(4)指向pre->next;
步骤三:pre指向cur;
步骤四:让dummyHead节点初始化pre节点
步骤五:最后让cur接收Xin节点的头结点即2

  while(cur !=NULL){
                while(pre->next !=NULL && pre->next->val < cur->val)
                {
                    pre=pre->next;
                }
                //在pre和prenext之间插入数据
                ListNode* Xin =cur->next;//步骤一:保存cur
                cur->next =pre->next;//步骤二
                pre->next =cur; //步骤三
                pre=dummyHead;//步骤四让dummyHead节点初始化pre节点,来找下一个插入位置
                cur =Xin;//步骤五:让cur接收Xin节点的头结点即2
            }

对链表进行插入排序,巧用虚拟头节点
接着读入2;
这个时候可以比较pre->next节点与cur节点的值大小,执行while循环。
不符合,然后跳出循环。
对链表进行插入排序,巧用虚拟头节点
还是按照前面五步骤法来,如下图:
对链表进行插入排序,巧用虚拟头节点

接着读入1;
这个时候可以比较pre->next节点与cur节点的值大小,执行while循环。
不符合,然后跳出循环。
对链表进行插入排序,巧用虚拟头节点
还是按照前面五步骤法来,如下图:
对链表进行插入排序,巧用虚拟头节点
接着读入3;
这个时候可以比较pre->next节点与cur节点的值大小,执行while循环。
符合,不断移动pre到2,如下图:
对链表进行插入排序,巧用虚拟头节点
还是按照前面五步骤法来,如下图:
对链表进行插入排序,巧用虚拟头节点

此时,cur为NULL,跳出整个while循环。
对链表进行插入排序,巧用虚拟头节点

输出dummyHead->next的节点即可。

完整代码:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
            if(head==NULL)  return head;
            ListNode* dummyHead = new ListNode(0);//定义一个虚拟头结点,并设置为0
            ListNode* cur = head;
            ListNode* pre = dummyHead;

            while(cur !=NULL){
                while(pre->next !=NULL && pre->next->val < cur->val)
                {
                    pre=pre->next;
                }
                //在pre和prenext之间插入数据
                ListNode* Xin =cur->next;//步骤一:保存cur
                cur->next =pre->next;//步骤二
                pre->next =cur; //步骤三
                pre=dummyHead;//步骤四让dummyHead节点初始化pre节点,来找下一个插入位置
                cur =Xin;//步骤五:让cur接收Xin节点的头结点即2
            }
        return  dummyHead->next;
    }
};

本文地址:https://blog.csdn.net/qq_25953411/article/details/109880326