排序链表
@1 切割法
public ListNode sortList(ListNode head)
{
if(head==null)
{
return null;
}
ListNode dmHead=new ListNode(0);
dmHead.next=head;
ListNode p=head;
int len=1;
while (p.next!=null)
{
len++;
p=p.next;
}
for(int size=1;size<len;size<<=1)
{
ListNode cur=dmHead.next;
ListNode tail=dmHead;
while (cur!=null)
{
ListNode left=cur;
ListNode right=cut(cur,size);
cur= cut(right,size);
tail.next=merge(left,right);
while (tail.next!=null)
{
tail=tail.next;
}
}
}
return dmHead.next;
}
public ListNode cut(ListNode head,int n)
{
ListNode p=head;
/*while(p!=null&&n>0)*/
while (--n>0&&p!=null)
{
/*n--;*/
p=p.next;
}
if(p==null)
{
return null;
}
ListNode x=p.next;
p.next=null;
return x;
}
public ListNode merge(ListNode node1,ListNode node2)
{
ListNode dhead=new ListNode(0);
ListNode p=dhead;
while (node1!=null&&node2!=null)
{
if(node1.val<node2.val)
{
p.next=node1;
p=node1;
node1=node1.next;
}
else {
p.next=node2;
p=node2;
node2=node2.next;
}
}
if(node1==null)
{
p.next=node2;
}
else
{
p.next=node1;
}
return dhead.next;
}
@2 归并递归
public ListNode sortList(ListNode head) {
return mergeSort(head);
}
// 归并排序
private ListNode mergeSort(ListNode head){
// 如果没有结点/只有一个结点，无需排序，直接返回
if (head==null||head.next==null) return head;
// 快慢指针找出中位点
ListNode slowp=head,fastp=head.next.next,l,r;
while (fastp!=null&&fastp.next!=null){
slowp=slowp.next;
fastp=fastp.next.next;
}
// 对右半部分进行归并排序
r=mergeSort(slowp.next);
// 链表判断结束的标志：末尾节点.next==null
slowp.next=null;
// 对左半部分进行归并排序
l=mergeSort(head);
return mergeList(l,r);
}
// 合并链表
private ListNode mergeList(ListNode l,ListNode r){
// 临时头节点
ListNode tmpHead=new ListNode(-1);
ListNode p=tmpHead;
while (l!=null&&r!=null){
if (l.val<r.val){
p.next=l;
l=l.next;
}else {
p.next=r;
r=r.next;
}
p=p.next;
}
p.next=l==null?r:l;
return tmpHead.next;
}
@3 快排
public ListNode sortList(ListNode head) {
if(head==null||head.next==null) return head;
// 没有条件，创造条件。自己添加头节点，最后返回时去掉即可。
ListNode newHead=new ListNode(-1);
newHead.next=head;
return quickSort(newHead,null);
}
// 带头结点的链表快速排序
private ListNode quickSort(ListNode head,ListNode end){
if (head==end||head.next==end||head.next.next==end) return head;
// 将小于划分点的值存储在临时链表中
ListNode tmpHead=new ListNode(-1);
// partition为划分点，p为链表指针，tp为临时链表指针
ListNode partition=head.next,p=partition,tp=tmpHead;
// 将小于划分点的结点放到临时链表中
while (p.next!=end){
if (p.next.val<partition.val){
tp.next=p.next;
tp=tp.next;
p.next=p.next.next;
}else {
p=p.next;
}
}
// 合并临时链表和原链表，将原链表接到临时链表后面即可
tp.next=head.next;
// 将临时链表插回原链表，注意是插回！（不做这一步在对右半部分处理时就断链了）
head.next=tmpHead.next;
quickSort(head,partition);
quickSort(partition,end);
// 题目要求不带头节点，返回结果时去除
return head.next;
}
image.png
public ListNode deleteDuplicates(ListNode head)
{
if(head==null)
{
return null;
}
ListNode node = new ListNode(0);
node.next=head;
ListNode slow=node;
ListNode quick=node.next;
while (quick.next!=null)
{
if (quick.next != null && quick.val != quick.next.val)
{
quick = quick.next;
slow = slow.next;
}
else
{
if (quick.next == null)
{
return node.next;
}
while (quick.next != null && quick.val == quick.next.val)
{
quick = quick.next;
}
slow.next = quick.next;
if(quick.next!=null)
{
quick = quick.next;
}
else return node.next;
}
}
return node.next;
}
image.png
-
@Hashmap
public Node copyRandomList(Node head)
{
if (head == null) {
return head;
}
//map中存的是(原节点，拷贝节点)的一个映射
Map<Node, Node> map = new HashMap<>();
for (Node cur = head; cur != null; cur = cur.next)
{
map.put(cur, new Node(cur.val));
}
//将拷贝的新的节点组织成一个链表
for (Node cur = head; cur != null; cur = cur.next)
{
map.get(cur).next = map.get(cur.next);
map.get(cur).random = map.get(cur.random);
}
return map.get(head);
}
-
@
public Node copyRandomList(Node head) {
if (head == null) {
return head;
}
//将拷贝节点放到原节点后面，例如1->2->3这样的链表就变成了这样1->1'->2'->3->3'
for (Node node = head, copy = null; node != null; node = node.next.next) {
copy = new Node(node.val);
copy.next = node.next;
node.next = copy;
}
//把拷贝节点的random指针安排上
for (Node node = head; node != null; node = node.next.next) {
if (node.random != null) {
node.next.random = node.random.next;
}
}
//分离拷贝节点和原节点，变成1->2->3和1'->2'->3'两个链表，后者就是答案
Node newHead = head.next;
for (Node node = head, temp = null; node != null && node.next != null;) {
temp = node.next;
node.next = temp.next;
node = temp;
}
return newHead;
}
