美文网首页
Leetcode上的链表问题

Leetcode上的链表问题

作者: 杭州痞老板 | 来源:发表于2018-06-05 10:48 被阅读0次
    package cn.infobuy.gouqi.demo;
    
    import cn.infobuy.gouqi.util.ListNode;
    import cn.infobuy.gouqi.util.TreeNode;
    
    /**
     * 关于链表
     * @author JohnLiu
     *
     */
    public class ListSolution {
        /**
         * 链表反转
         * @param head
         * @param m
         * @param n
         * @return
         */
        public ListNode reverseBetween(ListNode head, int m, int n) {
            ListNode current = head;
            int count = 0;
            ListNode partHead=null;
            ListNode partEnd=null;
            while(current!=null) {
                // 表示当前的节点是第counter个节点
                count++;
                if(count==m-1) {
                    partHead=current;
                }
                if(count==n+1) {
                    partEnd=current;
                }
                current = current.next;
            }
            if(partHead==null) {
                return reverseList(head, partEnd);
            }else {
                ListNode newPartHead = reverseList(partHead.next, partEnd);
                partHead.next=newPartHead;
                return head;
            }
        }
        /**
         * 旋转链表
         * 给定一个链表,将链表每个节点向右移动 k 个位置,其中 k 是非负数。
         * @param head
         * @param k
         * @return
         */
        public ListNode rotateRight(ListNode head, int k) {
            if (head == null || k <= 0) {
                return head;
            }
            ListNode current = head;
            int n = 1;
            //O(n)
            while (current.next != null) {
                n++;
                current = current.next;
            }
    
            current.next = head;
    
            int count = n - k % n;
            ListNode result = null;
            for (int i = 0; i < count; i++) {
                current = current.next;
            }
            result = current.next;
            current.next = null;
            return result;
        }
        /**
         * k个一组翻转链表
         * 递归版本
         * @param head
         * @param k
         * @return
         */
        public ListNode reverseKGroup1(ListNode head, int k) {
            ListNode current_node = head;
            int count = 0;
            while (current_node != null && count != k) {
                current_node = current_node.next;
                count++;
            }
            if (count == k) {
                current_node = reverseKGroup(current_node, k);/// 递归的解决子问题
                while (count-- > 0) {
                    ListNode temp = head.next;
                    head.next = current_node;
                    current_node = head;
                    head = temp;
                }///最终,该段的所有节点将会截空,head应指向current_node
                head = current_node;
            }
            return head;        
       }
        /**
         * k个一组翻转链表
         * 迭代版本
         * @param head
         * @param k
         * @return
         */
        public ListNode reverseKGroup(ListNode head, int k) {
            ListNode finalhead = new ListNode(0);
            finalhead.next=head;
            ListNode partHead = null;
            ListNode partNextHead = head;
            ListNode parent = finalhead;
            while((partHead=partNextHead)!=null){
                // 迭代寻找 partNextHead
                int tmpK = k-1;
                while((partNextHead=partNextHead.next)!=null&&tmpK>0){
                    tmpK--;
                }
                if(tmpK>0){
                    break;
                }
                reverseList(parent,partHead,partNextHead);
                parent=partHead;
            }
            return finalhead.next;
        }
        /**
         * 通过三个指针实现整个链表[head,endTarget.pre]的翻转
         * head:记录链表的头部
         * surplexHead: 记录链表剩余的头部
         * next:当前操作的节点
         * @param head
         * @return
         */
        public ListNode reverseList(ListNode head,ListNode end){
            ListNode currentNode = null;
            ListNode surplexHead = head;
            // 一个head指针专门记录处理完成后的head节点
            head=end;
            while(surplexHead!=end){
                currentNode = surplexHead;
                surplexHead=currentNode.next;
                currentNode.next=head;
                head=currentNode;
            }
            return head;
        }
        public void reverseList(ListNode parent,ListNode head,ListNode end){
            // 当前操作的指针
            ListNode currentNode = null;
            // 未操作的头指针
            ListNode surplexHead = head;
            // 已操作好的头指针
            head=end;
            while(surplexHead!=end){
                currentNode = surplexHead;
                surplexHead=surplexHead.next;
                currentNode.next=head;
                head=currentNode;
            }
            parent.next=head;
        }
        /**
         * 合并两个有序链表为一个有序链表
         * @param l1
         * @param l2
         * @return
         */
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            if(l1==null&&l2==null){
                return null;
            }
            if(l1==null){
                return l2;
            }
            if(l2==null){
                return l1;
            }
            if(l1.val>l2.val){
                l2.next=mergeTwoLists(l1,l2.next);
                return l2;
            }else{
                l1.next=mergeTwoLists(l1.next,l2);
                return l1;
            }
        }
        /**
         * 合并K个排序链表
         * 合并2个会的,那合并k个呢?
         * 
         * @param lists
         * @return
         */
        public ListNode mergeKLists(ListNode[] lists) {
            if (lists==null||lists.length==0){
                return null;
            }
            return mergeLists(lists,0,lists.length-1);
        }
        /**
         * 利用归并排序的思想
         * k个列表,每次拆成2堆,然后每堆生成一个排序后的链表,再将两个排序后的链表升为一个链表并返回
         * 时间复杂度为 O(lg(K)kn)
         * @param lists
         * @param left
         * @param right
         * @return
         */
        private ListNode mergeLists(ListNode[] lists, int left, int right) {
            int mid = (left+right)/2;
            if (left<right){
                ListNode l1 = mergeLists(lists, left, mid);
                ListNode l2 = mergeLists(lists, mid + 1, right);
                return mergeTwoLists(l1,l2);
            }
            return lists[left]; //如果left==right则直接返回左面的链表
        }
        /**
         * 删除链表的倒数第N个节点
         * @param head
         * @param n
         * @return
         */
        public ListNode removeNthFromEnd(ListNode head, int n) {
            ListNode reachEnd=head;
            ListNode reachNth=head;
            int depth=n;
            // 确保 reachEnd 比 reachNth 快 n步
            while(depth>=1){
                reachEnd=reachEnd.next;
                depth--;
            }
            ListNode markPreNode = null;
            while(reachEnd!=null){
                reachEnd=reachEnd.next;
                markPreNode=reachNth;
                reachNth=reachNth.next;
            }
            if(head==reachNth){
                // 如果head被删除了
                return head.next;
            }else{
                markPreNode.next=reachNth.next;
                return head;
            }
        }
        /**
         * 两两交换链表中的节点
         * 给定 1->2->3->4, 你应该返回 2->1->4->3.
         * @param head
         * @return
         */
        public ListNode swapPairs(ListNode head) {
            if(head==null||head.next==null){
                return head;
            }
            ListNode a = new ListNode(0);
            a.next=head;
            head=a;
            while(head.next!=null&&head.next.next!=null){
                ListNode nextNode=head.next.next;
                ListNode firstNode = head.next;
                // swapPairs
                firstNode.next=nextNode.next;
                head.next=nextNode;
                nextNode.next=firstNode;
                // 迭代
                head=firstNode;
            }
            return a.next;
        }
        /**
         * 删除排序链表中的重复元素
         * @param head
         * @return
         */
        public ListNode deleteDuplicates(ListNode head) {
            ListNode l1 = head;
            //验证 head.next 是否要加入
            while(head!=null&&head.next!=null){
                if(head.next.val==head.val){
                    head.next=head.next.next;
                }else{
                    head = head.next;
                }
            }
            return l1;
        }
        /**
         * 删除排序链表中的重复元素 II
         * @param head
         * @return
         */
        public ListNode deleteDuplicates2(ListNode head) {
            // 标记头节点
            ListNode parent = new ListNode(-1);
            ListNode certainTail = parent;
            // 第一个节点暂定为head
            certainTail.next=head;
            // 指定目前暂定的节点,考虑是否要加入certainTail链表中
            ListNode tmpTail = head;
            while(tmpTail!=null&&tmpTail.next!=null) {
                if(tmpTail.val!=tmpTail.next.val) {
                    certainTail.next=tmpTail;
                    certainTail=tmpTail;
                    tmpTail=tmpTail.next;
                }else {
                    while(tmpTail.next!=null&&tmpTail.val==tmpTail.next.val) {
                        tmpTail.next=tmpTail.next.next;
                    }
                    tmpTail=tmpTail.next;
                    certainTail.next=tmpTail;
                }
            }
            return parent.next;
        }
        /**
         * 分隔链表
         * 给定一个链表和一个特定值 x,对链表进行分隔,使得所有小于 x 的节点都在大于或等于 x 的节点之前。
         * 你应当保留两个分区中每个节点的初始相对位置。
         * @param head
         * @param x
         * @return
         */
        public ListNode partition(ListNode head, int x) {
            if(head==null) {
                return null;
            }
            ListNode top = head;
            ListNode current = null;
            // 验证head.next是否满足条件
            while(head.next!=null) {
                if(head.next.val<x) {
                    current=head.next;
                    head.next=head.next.next;
                    current.next=top;
                    top=current;
                }else {
                    head = head.next;
                }
            }
            return top;
        }
        public ListNode partition2(ListNode head, int x) {
            ListNode top = new ListNode(0);
            top.next=head;
            head=top;
            ListNode current = null;
            ListNode newHead = null;
            ListNode newTail = null;
            // 验证head.next是否满足条件
            while(head.next!=null) {
                if(head.next.val<x) {
                    current=head.next;
                    head.next=head.next.next;
                    if(newHead==null) {
                        newHead = current;
                        newTail = current;
                    }else {
                        newTail.next=current;
                        newTail = current;
                    }
                }else {
                    head = head.next;
                }
            }
            if(newHead!=null) {
                newTail.next=top.next;
            }else {
                newHead = top.next;
            }
            return newHead;
        }
        /**
         * 将有序链表转为二叉树BST
         * @param head
         * @return
         */
        public TreeNode sortedListToBST(ListNode head) {
            return sortedListToBST(head,null);
        }
        public TreeNode sortedListToBST(ListNode head,ListNode end) {
            if(head==end) {
                return null;
            }
            ListNode fast = head;
            ListNode slow = head;
            while(fast!=end&&fast.next!=end) {
                fast = fast.next.next;
                slow = slow.next;
            }
            TreeNode c = new TreeNode(slow.val);
            c.left=sortedListToBST(head,slow);
            c.right=sortedListToBST(slow.next,end);
            return c;
        }
    }
    
    

    相关文章

      网友评论

          本文标题:Leetcode上的链表问题

          本文链接:https://www.haomeiwen.com/subject/cglpsftx.html