class Solution {
public:
//我熟悉链表插入操作，因此采用插入排序，需要三指针保证链表完整性。
//对链表进行原地翻转,不需要额外空间
ListNode* sortList(ListNode* head) {
if (head == NULL || head->next == NULL)
{
return head;
}
ListNode dummyHead(-1,head); //固定头节点，保持头节点位置保持不变。
ListNode * pbefore =&dummyHead; //单链表插入，必须知道前面一个节点。不然无法完成插入操作，删除可以
ListNode* ptail = head ;//假设第一个节点已经排序完毕。
ListNode* pcur = head->next; //当前节点 ，这是未知元素。
while (pcur)
{
if(pcur->val >= ptail->val)
{
//case01-如果递增数据
ptail = pcur; //有序链表范围扩大。
pcur =pcur->next;
}else
{
//case02 当前元素在有序链表中位置
pbefore =&dummyHead;// 寻找pur前面一个元素位置
while (pcur->val > pbefore->next->val)
{
pbefore =pbefore->next;
}
//节点翻转
//pbefore ptail pcur
//| | |
//| | |
//head--- 5 -- 4 --- 3 --2 ---1
//01 删除pcur元素 4
ptail->next =pcur->next; //5————>3
//02 为了保证链表不被破坏 追究一元素 /4--->5
pcur->next =pbefore->next;
//03 为了保证链表不被破坏 追究一元素 // tail->4
pbefore->next = pcur;
pcur = ptail->next;//04 移动操作。
}
}
return dummyHead.next;
}
};
刷题收获--扩展知识
6个位操作
真真假假 假假真真
当n等于2的次幂时，"hash%n"和"hash&(n-1)"等
https://blog.csdn.net/valada/article/details/103951139
如何实现 hashCode() 结果再和它的高 16 位异或操作？
h >>> 16，将 hashCode() 结果无符号右移，所得结果高 16 位移到低 16 位
，而高 16 位都变为 0
(h = key.hashCode()) ^ (h >>> 16)，再将 hashCode()
结果和无符号右移的结果进行异或
这样所得结果的低 16 位就和 hashCode() 的所有位相关。
当再进行 hash & (length - 1) 运算，length 小于 65536 时，结果就更加散列。
hash & (length - 1)，
当 length = 2n 时，hash & (length - 1) 的结果和 hash 值的低 n 位相
