leetcode147对链表进行插入排序

题目:

对链表进行插入排序。

插入排序算法：

插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。

每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。

重复直到所有输入数据插入完为止。

示例 1：

输入: 4->2->1->3

输出: 1->2->3->4

示例 2：

输入: -1->5->3->4->0

输出: -1->0->3->4->5

思路:

1.因为不是双链表，所以无法像线性表一样从尾部比较的，插入，所以只能从排序好的地方从头开始比较

2.为了更方便，我可以设置一个指针指向排列好的队伍的最后一个，当要比较的节点值，比那个指针大，直接就排列好了，

否则就进入内层循环

3.内层循环就是老路子，从头开始遍历，之后插入

4.这里有个坑就是它的头可能会变，所以不可能只指向head的那个头节点，要重新设定一个伪头指针，确定第一个的位置。

代码：

/**

 * 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) {

      ListNode* dummy=new ListNode(0);

      ListNode* pre;

      dummy->next=head;

      while(head&&head->next)

      {

          if(head->val<head->next->val)

          {

              head=head->next;

              continue;

          }

          pre=dummy;

          while(pre->next->val<head->next->val)

          {

              pre=pre->next;

          }

          ListNode* cur=head->next;

          head->next=cur->next;

          cur->next=pre->next;

          pre->next=cur;

      }

      return dummy->next;

    }

};

巴特西

leetcode147对链表进行插入排序

题目:

思路:

代码：

最新文章

热门文章