<习题集><LeetCode><链表><61/83/82/86/92>

2023-12-13 04:49:50

目录

61. 旋转链表

83. 删除排序链表中的重复元素

82. 删除排序链表中的重复元素 II

86. 分隔链表

92. 反转链表 II



61. 旋转链表

https://leetcode.cn/problems/rotate-list/

    public ListNode rotateRight(ListNode head, int k) {
        //k等于0,或者head为空,直接返回head;
        if(k == 0 || head == null){
            return head;
        }
        //创建last用于记录尾节点,移动last找到尾节点,同时计算链表长度n;
        ListNode last = head;
        int n = 1;
        while(last.next != null){
            n++;
            last = last.next;
        }
        //k取模,避免重复翻转的情况;
        k = k%n;
        //k等于0,不用翻转直接返回head;
        if(k == 0){
            return head;
        }
        //创建移动的指针节点,找到开始翻转的节点的前一个节点;
        ListNode cur = head;
        int step = n-k;
        for(int i=step-1;i>0;i--){
            cur = cur.next;
        }
        //记录开始翻转的节点,这个节点就是返回的新链表的头节点。
        ListNode root = cur.next;
        //将尾节点和头节点连接;
        last.next = head;
        //截断开始翻转的前一个节点;
        cur.next = null;

        return root;
    }

83. 删除排序链表中的重复元素

https://leetcode.cn/problems/remove-duplicates-from-sorted-list/

    public ListNode deleteDuplicates(ListNode head) {
        //head为空,直接返回head;
        if (head == null) {
            return head;
        }
        //创建一个用于移动的指针节点;
        ListNode cur = head;
        //遍历链表,下一节点为空时,代表遍历完成;
        while (cur.next != null) {
            //如果前后节点值相等,则将后节点删除,前节点指向更后一个节点;
            if(cur.val == cur.next.val){
                cur.next = cur.next.next;
            }else{
                //否则向后移动;
                cur = cur.next;
            }
        }

        return head;
    }

82. 删除排序链表中的重复元素 II

https://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii/

    public ListNode deleteDuplicates(ListNode head) {
        //如果链表为空,返回null;
        if(head == null){
            return null;
        }

        //创建一个用于移动的指针节点,这个节点初始位置在head前;
        ListNode cur = new ListNode(-1,head);
        //记录节点cur的初始位置,用于返回;
        ListNode root = cur;

        //当cur的后两个位置有值时;
        while(cur.next!=null && cur.next.next!=null){
            //判断两个值是否相等;
            if(cur.next.val == cur.next.next.val){
                //相等则记录前一个值;
                ListNode curNext = cur.next;
                //在后一个值存在的前提下,将前一个值不断和后一个值比较;
                while(curNext.next!=null && curNext.val == curNext.next.val){
                    //如果前后值相等,则前值后移;
                    curNext = curNext.next;
                }
                //通过上述循环,走到此处则是遇到前后值不同的两个节点了;
                //将移动的指针节点cur的next,指向这个不同的后值。
                cur.next = curNext.next;
            }else{
                //如果前后值不相等,则cur向后移动;
                cur = cur.next;
            }
        }
        //返回记录的节点;
        return root.next;
    }

86. 分隔链表

https://leetcode.cn/problems/partition-list/

    public ListNode partition(ListNode head, int x) {
        //如果链表为空,直接返回;
        if(head == null){
            return null;
        }
        //建立两个链表,分别存储小于x和大于等于x的节点;
        ListNode less = new ListNode(-1);
        ListNode lCur = less;
        ListNode greater = new ListNode(-1);
        ListNode gCur = greater;
        //移动head节点,根据head节点值的大小为上面两个链表分配节点;
        while(head != null){
            if(head.val < x){
                lCur.next = head;
                lCur = lCur.next;
            }else{
                gCur.next = head;
                gCur = gCur.next;
            }
            head = head.next;
        }
        //greater链表肯定是放在两个链表偏后的,将这个链表的尾部置空,避免环形链表;
        gCur.next = null;
        //如果less为空,直接返回greater链表,注意返回的是next;
        if(less.next == null){
            return greater.next;
        }else{
            //如果less不为空,将less链表的尾部指向greater链表后,返回;
            lCur.next = greater.next;
            return less.next;
        }
    }

92. 反转链表 II

https://leetcode.cn/problems/reverse-linked-list-ii/

    public ListNode reverseBetween(ListNode head, int left, int right) {
        //因为head有可能被改变,创建一个节点,指向head,用于返回;
        ListNode root = new ListNode(-1,head);
        //创建节点pre,并将pre移动到指定开始翻转的节点的前一个节点;
        ListNode pre = root;
        for (int i=0;i<left-1;i++) {
            pre = pre.next;
        }
        //创建一个节点cur,cur指向需要反转的第一个节点;
        //cur最终会转到需要反转的最后一个节点位置上;
        ListNode cur = pre.next;

        for(int i=0;i<right-left;i++){
            //先记录cur的下一个节点;
            ListNode curNext = cur.next;
            //将cur的下一节点指向下下个节点;
            cur.next = curNext.next;
            //将curNext的下一节点指向pre的下一节点;
            //注意不要指向cur,因为cur一直在移动;
            curNext.next = pre.next;
            //将pre的下一节点指向curNext;
            //因为每次curNext都会更新;
            //这代表pre的下一节点指向的节点会随着循环的进行逐渐指向right的那个节点;
            pre.next =curNext;
        }
        return root.next;
    }

文章来源:https://blog.csdn.net/zzy734437202/article/details/134870091
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。