算法总结之链表

MOKE 2019-03-07 PM 30℃ 1条

链表

环形链表

有一个整数val,如何在节点值有序的环形链表中插入一个节点值为val的节点,并且保证这个环形单链表依然有序
给定链表的信息,及元素的值A及val,请构造出这个环形链表,并插入该值。
测试样例:
[1,3,4,5,7],[1,2,3,4,0],2
返回:{1,2,3,4,5,7}
思路
(1)val 构造节点 a,判断A是否为空,为空则直接用 a 构造环形链表
(2)不为空,用A构造环形链表,判断 root 是否比 a 大,是则将 a 直接插入root之前
(3)不是则定义两个节点 left = root,right = left.next,遍历链表找到 val 比 right 小的地方,即为val要插入的地方;left.next = a,a.next = right,则完成有序插入

        /*
        public class ListNode {
            int val;
            ListNode next = null;
        
            ListNode(int val) {
                this.val = val;
            }
        }*/
        public class InsertValue {
            public ListNode insert(int[] A, int val) {
                ListNode a = new ListNode(val);
                //为空则直接用val构造环形链表
                if(A==null){
                    a.next = a;
                    return a;
                }
                //用A构造环形链表
                ListNode root = new ListNode(A[0]);
                ListNode temp = root;
                for(int i=1;i<A.length;i++){
                    ListNode next = new ListNode(A[i]);
                    temp.next = next;
                    temp = temp.next;
                }
                temp.next = root;
                if(val<=root.val){
                    a.next = root;
                    temp.next = a;
                    return a;
                }
                ListNode left = root;
                ListNode right = left.next;
                while(right!=null && right.val<val){
                    left = right;
                    right = right.next;
                }
                left.next = a;
                a.next = right;
                return root;
            }
        }

删除给定节点

1.实现一个算法,删除单向链表中间的某个结点,假定你只能访问该结点。
给定带删除的头节点和要删除的数字,请执行删除操作,返回删除后的头结点。链表中没有重复数字
思路:已知要删除节点为pNode,则另next=pNode.next,pNode.val=next.val,pNode.next = next.next,即直接将pNode变为下一个节点,并删除下一个节点(当要删除节点为尾节点时,则没有办法)

        /*
        public class ListNode {
            int val;
            ListNode next = null;
        
            ListNode(int val) {
                this.val = val;
            }
        }*/
        public class Remove {
            public boolean removeNode(ListNode pNode) {
                if (pNode == null) {
                    return false;
                }
                ListNode next = pNode.next;
                if (next == null) {//pNode为尾节点
                    return false;
                }
                pNode.val = next.val;
                pNode.next = next.next;
                return true;
            }
        }

链表的分化

对于一个链表,我们需要用一个特定阈值完成对它的分化,使得小于等于这个值的结点移到前面,大于该值的结点在后面,同时保证两类结点内部的位置关系不变。
给定一个链表的头结点head,同时给定阈值val,请返回一个链表,使小于等于它的结点在前,大于等于它的在后,保证结点值不重复。
测试样例:
{1,4,2,5},3
{1,2,4,5}
思路:遍历链表,将小于等于 val 的组成一个链表,大于 val 的组成另一个链表;在将两个链表连接起来

        /*
        public class ListNode {
            int val;
            ListNode next = null;
        
            ListNode(int val) {
                this.val = val;
            }
        }*/
        public class Divide {
            public ListNode listDivide(ListNode head, int val) {
                ListNode s = null;
                ListNode sh = null;//保存小于等于的头节点
                ListNode b = null;
                ListNode bh = null;//保存大于等于的头节点
                while(head!=null){
                    if(head.val<=val){
                        if(s==null){
                            s = head;
                            sh = head;
                        }else{
                            s.next = head;
                            s = s.next;
                        }
                    }else{
                        if(b==null){
                            b = head;
                            bh = head;
                        }else{
                            b.next = head;
                            b = b.next;
                        }
                    }
                    head = head.next;
                }
                if(sh!=null){
                    s.next = bh;
                    return sh;
                }
                return null;
            }
        }

打印链表公共部分

现有两个升序链表,且链表中均无重复元素。请设计一个高效的算法,打印两个链表的公共值部分。
给定两个链表的头指针headA和headB,请返回一个vector,元素为两个链表的公共部分。请保证返回数组的升序。两个链表的元素个数均小于等于500。保证一定有公共值
测试样例:
{1,2,3,4,5,6,7},{2,4,6,8,10}
返回:[2.4.6]
思路:比较两个链表节点值,哪个链表的节点值大则其节点移到下一节点;相等时保存节点值,并两个链表的节点都移到下一个节点

        public class Common {
            public int[] findCommonParts(ListNode headA, ListNode headB) {
                LinkedList<Integer> temp = new LinkedList<Integer>();
                if(headA==null||headB==null)
                    return null;
                while(headA!=null && headB!=null){
                    if(headA.val>headB.val){
                        headB = headB.next;
                    }else if(headA.val<headB.val){
                        headA = headA.next;
                    }else{
                        temp.add(headA.val);
                        headA = headA.next;
                        headB = headB.next;
                    }
                }
                int index = temp.size();
                int[] res = new int[index];
                for(int i=0;i<index;i++){
                    res[i] = temp.get(i);
                }
                return res;
            }
        }

链表的k逆序**

有一个单链表,请设计一个算法,使得每K个节点之间逆序,如果最后不够K个节点一组,则不调整最后几个节点。例如链表1->2->3->4->5->6->7->8->null,K=3这个例子。调整后为,3->2->1->6->5->4->7->8->null。因为K==3,所以每三个节点之间逆序,但其中的7,8不调整,因为只有两个节点不够一组。
给定一个单链表的头指针head,同时给定K值,返回逆序后的链表的头指针。
思路
(1)定义一个 count 用来计数,用以限制每 k 个节点就做一次逆序
(2)逆序 k 个节点的操作需要三个节点:pre=start,cur=start.next,next(保存cur.next的信息);cur.next = pre之后将三个节点全部下移一个节点
(3)对于第一组的逆序需要保存头部信息,而对于后面局部的逆序,还需要两个节点left,right 即 k 个节点的前后节点,才可以与原有的链表连接起来

        /*
        public class ListNode {
            int val;
            ListNode next = null;
        
            ListNode(int val) {
                this.val = val;
            }
        }*/
        public class KInverse {
            public ListNode inverse(ListNode head, int k) {
                if(k<2)
                    return head;
                ListNode root = head;
                ListNode start = null;
                ListNode left = null;
                ListNode next = null;
                int count = 1;
                while(root!=null){
                    next = root.next;
                    if(count==k){
                        start=(left==null?head:left.next);
                        head=(left==null?root:head);//保存第一次的头节点
                        resign(left,start,root,next);//子链表前一个keft和后一个next
                        left = start;//经过上面的逆序,start已经在最后
                        count = 0;
                    }
                    count++;
                    root = next;
                }
                return head;
            }
            private void resign(ListNode left,ListNode start,ListNode end,ListNode right){
                ListNode pre = start;
                ListNode cur = start.next;
                ListNode next = null;//用以保存cur后面的信息
                while(cur!=right){
                    next = cur.next;//保存信息
                    cur.next = pre;//重新链接
                    pre = cur;//节点后移
                    cur = next;//节点后移
                }
                if(left!=null)
                    left.next = end;
                start.next = right;
            }
        }

链表指定值清除

现在有一个单链表。链表中每个节点保存一个整数,再给定一个值val,把所有等于val的节点删掉。
给定一个单链表的头结点head,同时给定一个值val,请返回清除后的链表的头结点,保证链表中有不等于该值的其它值。请保证其他元素的相对顺序。
测试样例:
{1,2,3,4,3,2,1},2
{1,3,4,3,1}
思路
(1)定义两个节点,一个用来保存头节点 root,一个用来保存尾节点 tail
(2)遍历链表,判断值是否与val相等,相等则直接移到下一个节点
(3)不相等则初始化两个节点为头节点,从下一个节点开始,tail 指向不等于val的 head 节点,并更新为 head

        public class ClearValue {
            public ListNode clear(ListNode head, int val) {
                ListNode root = null;
                ListNode tail = null;
                while(head!=null){
                    if(head.val!=val){
                        if(root==null){
                            root = head;
                            tail = head;
                        }else{
                            tail.next = head;
                            tail = head;
                        }
                    }
                    head = head.next;
                }
                return root;
            }
        }

回文结构的链表

请编写一个函数,检查链表是否为回文。
给定一个链表ListNode* pHead,请返回一个bool,代表链表是否为回文。
测试样例:
{1,2,3,2,1}
返回:true
{1,2,3,2,3}
返回:false
思路
(1)定义两个节点 slow(移1),fast(移2)遍历链表获取中间节点 slow
(2)从 slow 开始逆序后半部分,然后从两边开始依次比较,不相等则直接返回 false,一直比较到中间节点则返回true
(3)将逆序的部分调整回来

        public class Palindrome {
            public boolean isPalindrome(ListNode pHead) {
                boolean res = true;
                //取得中间节点
                ListNode fast = pHead;
                ListNode slow = pHead;
                while(fast!=null){
                    slow = slow.next;
                    fast = fast.next;
                    if(fast!=null)
                        fast = fast.next;
                }
                //逆序后半部分
                ListNode pre = slow;;
                ListNode cur = pre.next;
                ListNode next = null;
                while(cur!=null){
                    next = cur.next;
                    cur.next = pre;
                    pre = cur;
                    cur = next;
                }
                slow.next = null;
                //比较左右两部分
                ListNode start = pHead;
                ListNode end = pre;
                while(start!=null && end!=null){
                    if(start.val!=end.val)
                        res = false;
                    start = start.next;
                    end = end.next;
                }
                //恢复后半部分
                cur = pre.next;
                while(cur!=null){
                    next = cur.next;
                    cur.next = pre;
                    pre = cur;
                    cur = next;
                }
                return res;
            }
        }

复杂链表的复制

输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点)。
思路
(1)遍历链表,以每个节点的值创建新节点,并添加在每个原节点的后面
(2)再次遍历新链表,设置新节点第二个指针的值
(3)还原链表,取出新节点形成复制链表

        /*
        public class RandomListNode {
            int label;
            RandomListNode next = null;
            RandomListNode random = null;
        
            RandomListNode(int label) {
                this.label = label;
            }
        }
        */
        public class Solution {
            public RandomListNode Clone(RandomListNode pHead)
            {
                if(pHead==null)
                    return null;
                RandomListNode list = pHead;
                //复制每个节点并将其添加在每个被复制的节点后面
                while(list!=null){
                    RandomListNode temp = new RandomListNode(list.label);
                    temp.next = list.next;
                    list.next = temp;
                    list = list.next.next;
                }
                //设置每个新节点的random
                list = pHead;
                while(list!=null){
                    if(list.random!=null){
                        list.next.random = list.random.next;
                    }else{
                        list.next.random = null;//如果原来的节点没有指向其它节点则复制的也没有
                    }
                    list = list.next.next;
                }
                //还原链表,取出所有新节点
                list = pHead;
                RandomListNode temp = null;
                RandomListNode res = null;
                RandomListNode tmp = null;
                while(list!=null){
                    temp = list.next;
                    list.next = list.next.next;
                    if(tmp==null){
                        res = temp;
                        tmp = temp;
                    }else{
                        tmp.next = temp;
                        tmp = tmp.next;
                    }
                    list = list.next;
                }
                return res;
            }
        }

判断链表是否由环

如何判断一个单链表是否有环?有环的话返回进入环的第一个节点的值,无环的话返回-1。如果链表的长度为N,请做到时间复杂度O(N),额外空间复杂度O(1)。
给定一个单链表的头结点head(注意另一个参数adjust为加密后的数据调整参数,方便数据设置,与本题求解无关),请返回所求值。
思路
(1)设置快慢指针,慢指针走一步,快指针走两步,如果中途快指针为空则说明不存在环,返回 -1
(2)否则,当慢指针与快指针相等时,另快指针回到链表头,快慢指针同时一步一步走,当快慢指针再次相等时,此时的节点即为进入环的第一个节点

        public class ChkLoop {
            public int chkLoop(ListNode head, int adjust) {
                if(head==null||head.next==null)
                    return -1;
                ListNode fast = head;
                ListNode slow = head;
                while(fast!=null){
                    slow = slow.next;
                    fast = fast.next;
                    if(fast!=null)
                        fast = fast.next;
                    else
                        return -1;
                    if(slow==fast)
                        break;
                }
                if(fast==null)
                    return -1;
                fast = head;
                while(fast!=slow){
                    fast = fast.next;
                    slow = slow.next;
                }
                return fast.val;
            }
        }

无环链表是否相交

现在有两个无环单链表,若两个链表的长度分别为m和n,请设计一个时间复杂度为O(n + m),额外空间复杂度为O(1)的算法,判断这两个链表是否相交。
给定两个链表的头结点headA和headB,请返回一个bool值,代表这两个链表是否相交。保证两个链表长度小于等于500。
思路
(1)相交:从某一节点开始一直到最后节点都相同(因为相同节点完全一样)
(2)先遍历长的链表,剩余部分与短的链表等长时,同时遍历两个

        /*
        public class ListNode {
            int val;
            ListNode next = null;
        
            ListNode(int val) {
                this.val = val;
            }
        }*/
        public class CheckIntersect {
            public boolean chkIntersect(ListNode headA, ListNode headB) {
                ListNode a = headA;
                ListNode b = headB;
                int lenA = getLen(a);
                int lenB = getLen(b);
                if(lenA>=lenB){
                    return isMeet(headA,headB,lenA-lenB);
                }else{
                    return isMeet(headB,headA,lenB-lenA);
                }
            }
            
            private boolean isMeet(ListNode big,ListNode small,int num){
                while(num>0){
                    big = big.next;
                    num--;
                }
                while(big!=null && big!=small){
                    big = big.next;
                    small = small.next;
                }
                if(big!=null){
                    ListNode node = big;//此节点为第一个相交节点
                    return true;
                }else{
                    return false;
                }
            }
            
            private int getLen(ListNode node){
                int len = 0;
                while(node!=null){
                    len++;
                    node = node.next;
                }
                return len;
            }
        }

有环链表是否相交

如何判断两个有环单链表是否相交?相交的话返回第一个相交的节点,不想交的话返回空。如果两个链表长度分别为N和M,请做到时间复杂度O(N+M),额外空间复杂度O(1)。
给定两个链表的头结点head1和head2(注意,另外两个参数adjust0和adjust1用于调整数据,与本题求解无关)。请返回一个bool值代表它们是否相交。
思路
(1)获取两个有环链表的入环节点,判断节点是否相等,相等则说明相交(无环部分相交)
(2)不相等,遍历其中一个环,若环中存在另一个入环节点,说明相交,否则不相交

        /*
        public class ListNode {
            int val;
            ListNode next = null;
        
            ListNode(int val) {
                this.val = val;
            }
        }*/
        public class ChkIntersection {
            public boolean chkInter(ListNode head1, ListNode head2, int adjust0, int adjust1) {
                ListNode p1 = chkLoop(head1);
                ListNode p2 = chkLoop(head2);
                if(p1==p2)
                    return true;
                else{
                    ListNode temp = p1.next;
                while(p1!=temp){
                    if(temp==p2)
                        return true;
                    temp = temp.next;
                }
                    return false;
                }
            }
            
            //查找第一个入环节点
            public ListNode chkLoop(ListNode head){
                ListNode fast = head;
                ListNode slow = head;
                while(fast!=null && fast.next!=null){
                    slow = slow.next;
                    fast = fast.next.next;
                    if(slow==fast)
                        break;
                }
                if(fast==null||fast.next==null)
                    return null;
                fast = head;
                while(fast!=slow){
                    fast = fast.next;
                    slow = slow.next;
                }
                return fast;
            }
        }

判断链表是否相交

给定两个单链表的头节点head1和head2,如何判断两个链表是否相交?相交的话返回true,不相交的话返回false。
思路
(1)判断是否有环,获得入环节点
(2)都无环则,相当于无环链表的判断;都有环,则相当于有环链表的判断;一个有环一个没换,则不相交
注:代码为前面两个问题的组合,这里就不在重复

标签: none

非特殊说明,本博所有文章均为博主原创。

评论啦~



唉呀 ~ 仅有一条评论


  1. test
    test

    测试邮箱

    回复 2020-01-05 16:00