[数据结构与算法]单链表快速排序，不直接交换值，不使用额外链表空间，原地交换节点

单链表快速排序，不直接交换值，不使用额外链表空间，原地交换节点

做了数组的快速排序后，想着试一下单链表的快速排序。菜鸟一个 还请指正
单链表快速排序，不直接交换值，不使用额外链表空间，原地交换节点。
单链表快速排序三种解决办法
（1） 直接交换值，相对简单
（2） 额外维护两个链表，用于存放大于基点的节点和小于基点的基点 最后链接
（3） 不直接交换值，不使用额外链表空间，原地交换节点。较为复杂
我的思路：
分区函数中维护多个指针
index: 用于表示基点的正确位置，维护index左边都是小于基点的值
pre : index的前驱节点，原地交换节点时使用，同时作为函数返回值返回，表示左区间的结束节点
curr : 用于遍历节点
prec : curr的前驱节点，原地交换节点时使用，
分区函数返回值：
next : 基点的下一个节点，作为函数返回值返回，表示右区间的开始节点
left : 新的开始节点，因为链表经过分区操作后，开始节点不在是原先的节点
right: 新的结束节点，因为链表经过分区操作后，结束节点不在是原先的节点

作者：pang-hou-n
链接：https://leetcode-cn.com/problems/sort-list/solution/dan-lian-biao-kuai-su-pai-xu-bu-zhi-jie-gpi6v/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

func sortList(head *ListNode)*ListNode{
	preHead:=&ListNode{
		-1,
		head,
	}
	right:=head
	for right.Next!=nil{
		right=right.Next
	}

	preHead=NodesQuicSort(preHead,head,right)
	return preHead.Next
}

func NodesQuicSort(preHead,left,right *ListNode)*ListNode{
	if(left!=right){
		mid:=left
		left,pre,next,right:=partition_02(left,right)
		preHead.Next=left
		NodesQuicSort(preHead,left,pre)
		NodesQuicSort(mid,next,right)
	}

	return preHead
}

func partition_02(left,right *ListNode)(*ListNode,*ListNode,*ListNode,*ListNode){
	// 基点，取开始点为基点
	povitNode:=left
	
	// 用于保存最后基点的位置，即index左边的都是小于基点的
	index:=left.Next
	
	// 用于遍历
	curr:=index
	
	// curr的前驱指针
	prec:=left
	
	// index的前驱指针
	pre:=povitNode
	
	// 记录传进来的结束节点，用于终止遍历
	end:=right.Next
	
	// 开始遍历
	for curr!=end{
		if curr.Val<povitNode.Val{
			
			// curr可能和index指向同一个节点
			// 1.指向的不是同一个节点是，交换index和curr节点
			if curr!=index{
				// 其实这部分是交换节点
				temp:=index.Next
				index.Next=curr.Next
				curr.Next=temp
				
				// 这部分是要交换后保持链表正常连接
				pre.Next=curr
				pre=pre.Next
				prec.Next=index
				prec=index
				
				// 更新curr和index指针，进行下一轮循环
				temp=index.Next
				index=curr.Next
				curr=temp
			}else{
				// 2.指向同一个节点时，前进一个即可
				pre=index
				index=index.Next
				prec=curr
				curr=curr.Next
			}
		}else{
			prec=curr
			curr=curr.Next
		}
	}

	// 更新末尾节点
	right=prec
	
	// 将基点放在合适的位置
	// 1.当pre==povitNode 说明遍历的所有值都大于基点 基点位置不变
	if pre!=povitNode{
		left=povitNode.Next
		povitNode.Next=index
		pre.Next=povitNode
	}
	// next是基点的后一个节点 用于分区
	next:=povitNode.Next
	
	// 特殊情况 如果基点的后一个节点为终止节点 说明基点放在了最后一位 
	// 则把末尾节点更新为基点 并把基点的下一个节点更新为末尾节点 这样表明右分区遍历完了
	if(povitNode.Next==end){
		right=povitNode
		next=right
	}

	return left,pre,next,right
}