链表经典面试题

题目一

题目中的不能改变原来数据的顺序是指原来的12在23的后面，45在56的前面，重新按要求排序之后，12也要在23的后面，45也要在56的前面。

解题思路：我们可以通过区域化分的思路去解决，就是要值域小于x的节点位于一个区域，让值域大于x的节点为与另一个区域，最后在将这两个区域连接起来。

如上图，我们将链表值域小于x的的节点放在bs和be的区域，将链表中大于或等于x的值放在as和ae的区域，最后再将两条链表链接即可。

注意事项：我们在最后的拼接链表的过程中要判断bs和be是否为空，否则在执行be.next=as（拼接链表）的时候 会报错，最后如果as和ae不为空的话，我们都要将ae.next变为null。

完整代码：

public ListNode partition(ListNode pHead, int x) {// write code hereListNode bs = null;ListNode be = null;ListNode as = null;ListNode ae = null;ListNode cur = pHead;while (cur != null) {if (cur.val < x) {//第一次插入if (bs == null) {bs = cur;be = cur;cur = cur.next;} else {be.next = cur;cur = cur.next;be = be.next;}} else {//第一次插入if (as == null) {as = cur;ae = cur;cur = cur.next;} else {ae.next = cur;cur = cur.next;ae = ae.next;}}}//将链表拼接//要考虑bs到be区域为空的情况if (bs == null) {return as;}//代码运行到这里bs到be就不为空be.next = as;//如果as不为null，最后要将拼接后的最后一个节点的next置为nullif (as != null) {ae.next = null;}return bs;}

题目二

题目链接：链表的回文结构_牛客题霸_牛客网 (nowcoder.com) 

判断链表是否为回文结构

解题思路：我们可以先寻找链表的中间节点，接着将中间节点后面的节点进行翻转，最后进行回文判断。

 完整代码

public boolean chkPalindrome(ListNode A) {// write code hereif(A==null){return true;}//寻找中间节点ListNode fast=A;ListNode slow=A;while(fast!=null&&fast.next!=null){slow=slow.next;fast=fast.next.next;}//翻转链表ListNode cur=slow.next;while(cur!=null){ListNode curN=cur.next;cur.next=slow;slow=cur;cur=curN;}//判断回文结构//这里记得要用slow//因为在节点个数为偶数时,fast会为nullwhile(A!=slow){if(A.val!=slow.val){return false;}A=A.next;slow=slow.next;//考虑节点个数为偶数个if(A.next==slow){return true;}          }return true;}

我犯过的错误

链表翻转那里出现过问题。

题目三

题目链接：160. 相交链表 - 力扣（LeetCode） 

两个链表有交点是指两条链表之间，有一条短的链表的最后一个节点的next与另一条长的链表中的一个节点的next指向相同，并不是指有节点中值域相同的值。

如下图

这道题有两种情况，分别是链表的交点之前的节点个数相同或者不同的情况。

第一种情况：交点之前的节点个数相同

解题思路：我们分别让两个头节点同时向后走，知道他们走到交点。

如下图

第二种情况：交点前面的节点个数不同

解题思路：我们先让长的链表先走长短链表长度的差值步，然后再同时向后走到交点。

如上图，下面链表交点之前的节点个数比上面那条链表的节点个数多一个，所以先让下面的链表先走一步，然后再让两条链表同时向后走，知道走到链表的交点。

完整解题思路：

我们分别计算两条链表的长度，求差值，然后再对那条链表更长进行验证，同时设置一个pl变量指向长链表，ps指向短链表，然后让长链表先走差值步，然后再让两条链表同时先后走，知道走到交点。

完整代码：

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode cur1=headA;//链表A的长度int lenA=0;while(cur1!=null){lenA+=1;cur1=cur1.next;}ListNode cur2=headB;int lenB=0;while(cur2!=null){lenB+=1;cur2=cur2.next;}int len=lenA-lenB;//分别设置变量记录长短链表ListNode pl=headA;//pl代表长链表ListNode ps=headB;//ps代表短链表if(len<0){len=lenB-lenA;pl=headB;ps=headA;}//让长链表走差值步while(len!=0){pl=pl.next;len--;}while(ps!=pl){ps=ps.next;pl=pl.next;}//没有相交的情况if(ps==null || pl==null){return null;}return pl;}

感谢观看！！！