编程导航通关算法村第一关|白银挑战

偏执的太偏执、 2024-02-21 10:12 42阅读 0赞

## 两个链表第一个公共子节点 ##

题目：剑指offer52：输入两个链表，找到它们的第一个公共节点。

例如下面的两个链表：

![1fd451e5c96d478a8167df67fc7b0b97.png][]

两个链表的头结点已知，相交之后成为一个单链表，但是相交的位置不知，并且相交之前的结点数也是为止的，请设计算法找到两个链表的合并点。

分析：首先链表的特点在于可以有多个前驱，但是只能有一个后继，这样设计是为了保证链表的顺序性。所以重合滞后只能形成一个单链表。

无思路先遍历常用数据结构和算法。

常用数据结构有链表，数组，队，栈，集合等，常用算法有查找，排序，双指针等。

目前只学了链表，队，栈。

用栈解决：把链表压入两个栈中。一边出栈一边比较出栈元素是否一致，如果不一致，那么最晚出栈的就是第一个公共结点。

Java代码实现

public class FindFirstComminNode{
        public static void main(String[] args){
            ListNode[] heads=initLinkedList();
            ListNode la=heads[0];
            ListNode lb=heads[1];
    
            /**
             * 栈
             */
            public FindFirstCommonNodeByStake(ListNode headA,ListNode headB){
                //这里，Stack<ListNode> 表示一个泛型类型的栈，其中 ListNode 是存储在栈中的元素的类型。<> 表示泛型类型的参数列表。
                Stack<ListNode> stackA=new Stack();
                Stack<ListNode> stackB=new Stack();
                //入栈
                while(headA!=null){
                    stackA.push(headA);
                    headA=headA.next;
                }
                while(headB!=null){
                    stackB.push(headB);
                    headB=headB.next;
                }
                //匹配
                //创建一个临时结点用于存储最新弹出的栈元素
                ListNode preNode=null;
                while(stackA.size()>0&&stackB.size()>0){
                    if(stackA.peek()==stackB.peek()){
                        preNode=stackA.pop();
                        stackB.pop();
                    }else{
                        break;//如果不一致说明前一个结点一定是第一个公共结点
                    }
                }
                return preNode;
            }
        }
    }

## 判断链表是否为回文序列 ##

回文是指正着读和倒着读都一样的词、短语、句子或数字符号。也就是说，无论从左到右还是从右到左阅读，其字符序列都是相同的。

借用栈来逆序，首先将链表全部压入栈，顺便得到总长度，然后一边出栈，一边遍历链表。只需要遍历数组一半就可以。

public static boolean isPalindromeByHalfStack(ListNode head) {
            if (head == null)
                return true;
            //遍历链表长度
            ListNode cur = head;
            int count = 0;
            Stack<Integer> stackA = new stack<>();
            while (cur!= null) {
                count++;
                cur = cur.next;
                stackA.push(cur.val);
            }
            //将count除以2
            count >>= 1;
            while (count-- > 0) {//count=0说明栈空，count从1计数。
                if (stackA.pop() != head.val)
                    return false;
                head = head.next;
            }
            //如果栈空说明是回文序列
            return true
        }

再改进一点，先将链表遍历得到总长度，将一半链表压栈，此时链表恰好到中点，然后将后半部分链表与栈比较，但是这有个问题在于如果是长度为奇数，那么链表需要再跳过一个结点，如果长度为偶数则不需要。

或者反转链表，重新遍历两个链表。

## 合并有序列表 ##

### 1.合并2个有序列表 ###

思路：

1）新建一个链表，然后分辨遍历两个链表选取最小结点接入到链表上，最后排完。

2）把其中一个链表结点接入到另外一个链表上。

public static ListNode mergeTwoListsMoreSimple(ListNode l1, ListNode l2) {
           //创建一个新链表,表头按住不动，另设一个结点指向当前结点，有点像压缩字符串中的双指针。
            ListNode predHead=new ListNode(0);
            ListNode pred=predHead;
            while(L1!=null&&L2!=null){
                if(l1.val< l2.val){
                    pred.next=l1;
                    l1=l1.next;
                }else{
                    pred.next=l2;
                    l2=l2.next;
                }
                //更新
                pred=pred.next;
            }
            //至多还有1个未合并完，直接接上去
            pred.next=l1==null? l2:l1;
            //返回表头
            return predHead;
        }

2.合并k个有序列表

将2个写好后就能好很多。

实际上就是1和2合并成一条，去和3合并，不断重复将两条链表合并。

public static ListNode mergeKLists(ListNode[] lists){
            ListNode res=null;
            for(ListNode list:lists){
                res=mergeTwoLists(res,list);
            }
            return res;
        }

/**
         *list1下标从a到b节点删除，接入list2
         */
        public ListNode mergeInBetween(ListNode list1,ListNode list2,int a,int b){
            ListNode pre1=list1,post1=list1,post2=list2;
            int i=0,j=0;
            while(pre1!=null&&post1!=null&&j<b){
                if(i!=a-1){
                    pre1=pre1.next;
                    i++;
                }
                if(j!=b){
                    post1=post1.next;
                    j++;
                }
            }
            post1=post1.next;
            while(post2.next!=null)
                post2=post2.next;
            pre1.next=list2;
            post2.next=post1;
            return list1;
        }

[1fd451e5c96d478a8167df67fc7b0b97.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/aef705e2e5fb45128cd68451d338325e.png