亲宝软件园·资讯

展开

Java 链表

K稳重 人气:0

链表面试题一

判断链表是否是回文结构。

问题描述:

兄弟们,看图理解什么是链表的回文结构:

回文结构:正着读12 -> 23 ->34,倒着读12->23->34

奇数偶数都可以:

问题分析:

要判断是不是回文结构,那么我们就要遍历链表,一个从前往后走,一个从后往前走,对应的val值要相同,那么我们就必须修改链表的指向,这里就要用到快慢指针帮我们找到中间的节点,从中间节点开始改变指向,指向变更完成之后再开始遍历。

问题讲解:

第一步:为了确保始终能找到我们的链表,定义一个head变量一直指向头节点。

第二步:定义两个变量,开始都指向head,通过快慢指针的方法求出中间节点。

第三步:定义一个cur变量指向中间节点的后面一个节点,让cur变量来修改指向。

第四步:定义一个curNext变量等于cur.Next,防止改变指向后无法找到后面的节点。

代码实现:

  public boolean chkPalindrome(ListNode head) {
        if(head == null) return false;//判断一下链表是不是空,空的话直接返回false
        ListNode fast = head;//快指针fast,初始等于head
        ListNode slow = head;//慢指针slow,初始等于head
        while(fast != null && fast.next != null){//如果链表是奇数,fast.next == null停下,如果链表是偶数fast == null停下
            fast = fast.next.next;//fast走两步
            slow = slow.next;//slow走一步
 
        }
        ListNode cur = slow.next;//cur等于slow的下一个节点
        while(cur != null){//cur不为空开始反转
            ListNode curNext = cur.next;//curNext等于cur的下一个节点
            cur.next = slow;//开始反转
            slow = cur;//反转完了后让slow等于cur
            cur = curNext;//cur再往后走一步。
        }
        while(head != slow){//判断是不是回文结构
            if(head.val != slow.val){//不是回文结构
                return false;
            }
            if(head.next == slow){//偶数链表的情况
                return true;
            }
            head = head.next;
            slow = slow.next;
        }
        return true;
    }

链表面试题二

输入两个链表,找出它们的第一个公共结点。

问题描述:

问题分析:

判断:

1.如果两个链表是相交那么是Y还是X形状?  Y

2.如果两个链表相交,值val域相同还是next域相同?  next域相同

上图就是相交的链表。 

问题讲解:

第一步:先定义两个字节变量分别指向两个链表的头,headA和headB。

第二步:定义两个变量求出两条链表的差值。

第三步:再定义两个字节变量ps和pl分别指向headA和headB。

第四步:让长的链表先走他们的差值步。

第五步:两个链表再一起走。

第六步:当ps=pl的时候就是共同节点了。

代码实现:

 public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headB == null || headA == null) return null;//判断其中一条链表的头节点为空就是没有焦点
        ListNode ps = headA;
        ListNode pl = headB;
        int lenA = 0;
        int lenB = 0;
        while(ps != null){求出ps链表的长度
            lenA++;
            ps = ps.next;
        }
        ps = headA;//让ps重新等于头节点
        while(pl != null){求出pl链表的长度
            lenB++;
            pl = pl.next;
        }
        pl = headB;//让pl重新等于头节点
        int len = lenA - lenB;
        if(len < 0){//判断ps长还是pl长
            ps = headB;
            pl = headA;
            len = lenB - lenA;
        }
         while(len != 0)//求两条链表的差值
                ps = ps.next;
                len--;
 
            }
        while(ps != pl){
            
            ps = ps.next;
            pl = pl.next;
        }
        return ps;
    }

加载全部内容

相关教程
猜你喜欢
用户评论