排序鏈表
@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){
// 如果沒有結(jié)點/只有一個結(jié)點扁掸，無需排序带兜，直接返回
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);
// 鏈表判斷結(jié)束的標(biāo)志：末尾節(jié)點.next==null
slowp.next=null;
// 對左半部分進行歸并排序
l=mergeSort(head);
return mergeList(l,r);
}
// 合并鏈表
private ListNode mergeList(ListNode l,ListNode r){
// 臨時頭節(jié)點
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;
// 沒有條件勘畔，創(chuàng)造條件。自己添加頭節(jié)點艘刚，最后返回時去掉即可。
ListNode newHead=new ListNode(-1);
newHead.next=head;
return quickSort(newHead,null);
}
// 帶頭結(jié)點的鏈表快速排序
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;
// 將小于劃分點的結(jié)點放到臨時鏈表中
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);
// 題目要求不帶頭節(jié)點，返回結(jié)果時去除
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中存的是(原節(jié)點避除，拷貝節(jié)點)的一個映射
Map<Node, Node> map = new HashMap<>();
for (Node cur = head; cur != null; cur = cur.next)
{
map.put(cur, new Node(cur.val));
}
//將拷貝的新的節(jié)點組織成一個鏈表
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;
}
//將拷貝節(jié)點放到原節(jié)點后面怎披，例如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;
}
//把拷貝節(jié)點的random指針安排上
for (Node node = head; node != null; node = node.next.next) {
if (node.random != null) {
node.next.random = node.random.next;
}
}
//分離拷貝節(jié)點和原節(jié)點，變成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;
}
