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;
}加载全部内容