Java 深入分析链表面试实例题目

Java 深入分析链表面试实例题目

目录链表面试题一问题描述：问题分析：问题讲解：代码实现：链表面试题二问题描述：问题分析：问题讲解：代码实现：

链表面试题一

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

问题描述：

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

回文结构：正着读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;xLpIQWVREu//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;

http:// }

while(len != 0)//求两条链表的差值

ps = ps.next;

len--;

}

while(ps != pl){

ps = ps.next;

pl = pl.next;

}

return ps;

}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。