腾讯五十题 No.33 排序链表

题目链接
递归排序三部曲:①快慢指针找中点;②递归调用mergeSort; ③合并两个链表
归并

class Solution {
    public ListNode sortList(ListNode head){
        return mergeSort(head);
    }
    //归并排序
    private ListNode mergeSort(ListNode head){
        //如果没有节点、只有一个节点,无需排序
        if(head == null || head.next == null) return head;
        //快慢指针找中位点
        ListNode slow = head,fast = head.next.next,l,r;
        while(fast!=null && fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        //对右半部分进行归并排序
        r = mergeSort(slow.next);
        //判断链表是否结束
        slow.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;
    }
} 

快排(大佬说头条面到了)

class Solution {
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;
    }
}

推荐这些文章:

腾讯五十题 No.30

题目链接
因为需要用到fast.next.next所以必须确保fast!=null && fast.next!=null,才能走到fast = fast.next.next;
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode fast = head,slow = head;
while(fast!=null && fast.next!=null){
fast = fast.next.next;
...

腾讯五十题No.31 环形链表II

题目链接
判断环的入口,需要先判断有没有环,在寻找环的入口,找入口时需要重新定义两个”指针“,一个指向头节点,一个指向当前fast,让他们前进速度相同,他们想入的点即为入口。
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode fast = head,slow = head;
while(fast!=null && fast.next!=null){
fast = fast.next.next;
...

腾讯五十题 No.35 相交链表

题目链接
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA == null || headB == null) return null;
ListNode pa = headA,pb = headB;
while(pa != pb){
pa = pa != null? pa.next : headB;
pb = pb != null...

腾讯五十题 No.12 合并两个有序链表

题目链接
0ms
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
//如果某个list为空就直接返回零一list
if(list1==null) return list2;
if(list2==null) return list1;
if(list1.val<=list2.val){
list1.next = mergeTwoLists(list1.next,list2);
...

BM15 删除有序链表中重复的元素-I

/*
* function ListNode(x){
* this.val = x;
* this.next = null;
* }
*/

/**
*
* @param head ListNode类
* @return ListNode类
*/
function deleteDuplicates( head ) {
// write code here
if(head == null){
return null
}

if(head.next == null) {
return ...

链表逆转三种方式

static class Node {
int val;
Node next;

public Node(int val, Node next) {
this.val = val;
this.next = next;
}
}

static Node reverse(Node head) {
if (head.next == null) {
return head;
}

Node re...

LeetCode---24. 两两交换链表中的节点

题目:24. 两两交换链表中的节点
给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。
你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this...

第36天--算法(牛客网剑指offer3)

1.JZ23 链表中环的入口结点
public ListNode EntryNodeOfLoop(ListNode pHead) {   if(pHead == null || pHead.next == null || pHead.next.next == null) {     return null;   }   ListNode fast = pHead.next.next;   ListNode slow = pHead.next;   while(fast != slow) { ...

19. Remove Nth Node From End of List

!!!题目链接!!!
Solution:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class So...

Leetcode刷题之链表增加头结点的前缀节点

链表之增加头结点的前缀节点

在许多链表题中往往需要在题目给的头结点之前增加一个前缀节点
通常在删除链表和头结点需要交换时需要用到这一操作
因为增加这个节点就避免了对删除头结点这种特殊情况的特殊处理
而且往往在声明一个前缀节点之后再复制一个,前者保存不动用于最后结果返回,后者参与之后的操作

​ Leetcode203删除链表元素

给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点 。
输入:head = [1,2,6,3,4,5,6], val = 6
输出:head = [1,2,6,3,4,5,6]...

文章标题:腾讯五十题 No.33 排序链表
文章链接:https://www.dianjilingqu.com/51010.html
本文章来源于网络,版权归原作者所有,如果本站文章侵犯了您的权益,请联系我们删除,联系邮箱:saisai#email.cn,感谢支持理解。
THE END
< <上一篇
下一篇>>