链表精选题集
目录
我们做链表要学会用多指针
1 链表翻转
题目链接：
力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
解题：
首先我们假设一个链表里有三个节点：head指向第一个节点（头节点），cur指向第二个节点（需要翻转的节点），curNext指向第三个节点（将要被翻转的节点）；
此时cur.next = head就将第二个节点指向了第一个节点，由于第二个节点不指向第三个节点了，因此我们需要有一个curNext来访问第三个节点，防止后面节点丢失；之后将head = cur,这样head就重新指向第一个节点，cur = curNext，这样cur就指向了需要被翻转的节点，curNext = curNext.next，就将curNext指向了下一个被翻转节点。以此类推就可以实现链表翻转。
细节处理：我们完成了一般任务后就要考虑细节
1 当链表为空或者只有一个节点的时候就必独立写出来，因为此时curNext =? head.next.next会出现空指针异常；
2 代码倒数第二行，是将末尾指针的指向设为空，因为如果不设为空，链表就会出现循环；
注意：一个节点的next设置值（改变指向）或者null时一定要注意，因为链表是一连串的，假如我们将第二个节点的指向设置为空，此时如果没有指针指向第三个节点时，那么第三个节点和其后的都将丢失
试错版：
如果自己独立实现过头节点插入的伙伴一定首先想到的是这种方法：
即另外实例化一个链表，然后利用头插法，将原链表中的节点利用头插法依次插入到这个链表中，但是当我们运行后就会发现，最后得到的只有一个节点。
我们来分析一下原因：
上面说过，如果改变某一个节点的指向时，那么这个节点之后的可能就会丢失。我们看上图的代码：用cur依次取出原有链表中的节点，然后插入到新链表中，当插入的时候其中有一个node.next = head，这句话的意思是将cur节点指向head，注意head此时是新链表的head(如果不明白，那么在head前加个this就懂了，谁调用这个方法那么this就代表谁)，这个时候cur就指向了空，因为此时没有指针指向cur后面的节点，因此cur后面的节点就都丢失了。所以最后新旧链表都只剩下了第一个节点了；
注意：无论复制多少份链表，都是同一份链表，只要其中一个改变那么全部都会变。
2 找中间节点
题目链接:
力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
题解：
这种题方法很简单理解后就很容易记住了：
我们找中间数用的是双指针法：即有一个快指针和慢指针，快指针每次走两步，慢的每次走一步，通过简单分析，这里我们要分偶数个还是奇数个节点，此时循环的结束条件也就不一样。当节点偶数个时，那快指针为Null的时候，慢指针才能满足条件；当节点为奇数的时候，只需要在快指针的next（指向）为null时即可满足条件。注意这两个条件的先后，要先确保fast不为空，才能确保fast.next不会出现空指针异常。
最后讨论特殊情况即可。
3 找倒数第k个节点
题目链接：
链表中倒数第k个结点_牛客题霸_牛客网 (nowcoder.com)
public class Solution {
public ListNode FindKthToTail(ListNode head, int k) {
if(k<=0 || head == null) {
return null;
}
ListNode fast = head;
ListNode slow = head;
while (k > 1) {
fast = fast.next;
if (fast == null) {
return null;
}
k--;
}
while (fast.next != null) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
}题解：
这道题仍然用双指针。
一般思路是知道这个链表的节点个数，然后再通过循环找到倒数的节点。如果我们只用指针的话就无法得知节点个数，此时就需要解决两个问题，第一个如何判断k是否越界，第二个找到倒数第k个数。
我们的思路是有两个指针，当快指针走到最后一个节点的时候，我们发现所求节点离最后一个节点k-1步，这样我们就可以用快指针来当循环结束条件，当快指针指向最后一个节点的时候停止循环，此时假设慢指针指向所需求的节点，那么返回慢指针即可。那接下来我们怎么才能让循环停止的时候让慢指针指向所求节点，分析很容易得知，让快慢指针均指向头节点，快指针先走k-1步再一起走就可以了。
接下来是判断越界问题，如果k<=0那么直接返回null即可，但是当k大于节点个数的时候怎么办，仔细思考就会发现当我们让快指针走k-1步的时候就可以设置条件来判断k是否越界。
细节：在快指针先走的循环里，我们要先让fast = fast.next再去判断fast是否为null，因为如果先判断的话，这样就会导致循环结束fast正好为空，那么进入下一个循环判断fast.next的时候就会出现空指针异常，而且，我们在最先判断head不为null，也就确保了第一个循环里的fast = fast.next不会出现异常。
4 将两个升序链表合并为一个升序链表
题目链接：
力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
int count = 0;
if(list1 == null) {
return list2;
}
if(list2 == null) {
return list1;
}
ListNode newhead = new ListNode();
ListNode cur3 = newhead;
ListNode cur1 = list1;
ListNode cur2 = list2;
while(cur1 != null && cur2 != null) {
if(cur1.val < cur2.val) {
if(count == 0) {
cur3 = newhead = cur1;
count++;
}else{
cur3.next = cur1;
cur3 = cur3.next;
}
cur1 = cur1.next;
}else {
if(count == 0) {
cur3 = newhead = cur2;
count++;
}else{
cur3.next = cur2;
cur3 = cur3.next;
}
cur2 = cur2.next;
}
}
if(cur1 == null) {
cur3.next = cur2;
}else{
cur3.next = cur1;
}
return newhead;
}
}
题解：
这道题思路很常规，定义两个指针，比较并依次插入即可。不多赘述
5 给一个值来划分链表再组合
题目链接：
题解：
public class Partition {
public ListNode partition(ListNode pHead, int x) {
if(pHead == null) {
return null;
}
// write code here
ListNode ss = null;
ListNode se = null;
ListNode bs = null;
ListNode be = null;
ListNode cur = pHead;
while (cur != null) {
if (cur.val < x) {
if (ss == se && ss == null ) {
ss = se = cur;
} else {
se.next = cur;
se = cur;
}
} else {
if (bs == be && bs == null ) {
bs = be = cur;
} else {
be.next = cur;
be = cur;
}
}
cur = cur.next;
}
if (se != null ) {
if(be != null) {
be.next = null;
}
se.next = bs;
return ss;
} else {
return bs;
}
}
}
我们的思路是将小于x的节点放一边，大于等于的放另一边，最后让小于一边的最后一个节点去指向另一边的第一个节点。
这部分很简单：定义四个指针，分别指向一边的始尾.
ss指小于x的头节点，se指小于x的尾节点；
bs指大于x的头节点,be指大于x的尾节点；设置尾节点是为了好插入；
细节：
首先就是要考虑链表是否为空，是的话直接返回null;
再者我们要考虑如果节点均大于x的话，那么直接返回bs即可；
最隐匿的一个细节是，最后得到的链表它的尾部是否为null，如果不是就会循环，因此我们最后要手动置空，在置空的时候要判断be是否为空防止空指针。
6 判断链表是否是回文结构
题目链接：
链表的回文结构_牛客题霸_牛客网 (nowcoder.com)
题解：
public class PalindromeList {
public boolean chkPalindrome(ListNode A) {
// write code here
if (A == null) {
return false;
}
if (A.next == 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 curNext = cur.next;
cur.next = slow;
slow = cur;
cur = curNext;
if (curNext != null) {
curNext = curNext.next;
}
}
ListNode start = A;
while (start != null && slow != null) {
if (start.val != slow.val) {
return false;
}
if (start == slow || start.next == slow) {
return true;
}
start = start.next;
slow = slow.next;
}
return false;
}
}这道题是道综合题，方法都讲过，现在我们来看一下这道题思路：
判断是否回文，我们可以设置一个始尾指针，通过一个个比较进行判断；首先要想这么做那么我们必须翻转链表中间以后节点的指向，而找到中间节点又可以通过上面讲的快慢指针来寻找；
第一个循环是为了找到中间节点，将这个节点的指针设置为slow，而后设置两个cur和curNext来指向需要翻转和将要反转的指针；注意这个循环的结束条件不能是slow.next == null;(因为此时最后一个节点指向的是前一个节点，而不是Null)?;最后一步就是设置始尾指针来进行判断。注意这个循环的判断条件，当节点总数是奇数的时候，两个指针会相遇，那么当slow == start的时候可以结束循环，但是节点总数是偶数的时候判断起来就有一点难度，这个时候当我们画图可以知道，如果start.next == slow时，就可以结束循环。
其他情况：当链表为null或者只有一个节点的时候直接返回。
?7 判断链表是否相交并给出交点
题目链接：
力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
题解：
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
int l = 0;
int s = 0;
ListNode cur = headA;
while(cur != null) {
l++;
cur = cur.next;
}
cur = headB;
while (cur != null) {
s++;
cur = cur.next;
}
ListNode lNode = headA;
ListNode sNode = headB;
if(l - s < 0) {
int tem = s;
s = l;
l = tem;
lNode = headB;
sNode = headA;
}
int result =l - s;
while(result > 0) {
lNode = lNode.next;
result--;
}
while(lNode != null && sNode != null ) {
if(lNode == sNode){
return lNode;
}
lNode = lNode.next;
sNode = sNode.next;
}
return null;
}
}这道题就按常规思路来解题，我们要想判断两个链表是否相交，那我们就要看他们是否有相同的节点，如果有的话，那么这个节点及其以后的都一样，只是这个节点前的部分不一样，假设有个指针指向节点A，另一个指针指向节点B,如果两个链表相同节点前部分长度相同，那么只需要A，B走相同步数就可以走到相同节点，但是如果长度不一样差了n步，那么我们就可以先让长的链表先走n步，之后两个链表再一起走，如果A==B那么说明两个链表相交，否则不相交。
解释代码：
首先我们定义了l和s，来记录两个链表各自的长度，之后设置两个指针来分别指向A，B的头节点，为了确保lNode指向长链表的头结点，sNode指向短的，我们在中间加了一个if条件；之后设置一个循环让长链表的指针走n步，走完后；再设置一个循环，让长短指针一起走，能相遇返回节点，不能返回null.
8 判断链表是否循环
题目链接：
力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
题解：
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if(fast == slow) {
return true;
}
}
return false;
}
}这道题思路有点难：
如果链表不是循环那么，判断很简单，让指针不断指向下一个那么迟早会穷尽，但是如果链表循环，那么这样子就不行了，遇到链表问题没办法时可以从多指针下手，就容易拨云见日;
我们设置了两个指针，在一个圈内，不论时间，一个速度快的人总是能够追赶上一个速度慢的，同理在一个成环的链表里，快指针迟早会追赶上慢指针，这就是我们的思路。
解释代码：
我们设置了一个快指针和慢指针，设置循环，让快指针走两步，慢指针走一步，相遇返回true，不相遇那么循环迟早结束，返回null.
思考：为什么非要快指针走两步，慢指针走一步；这是个数学问题，大家可以想一下；
感兴趣的可一看一下：
进阶问题：找到循环的入口点（数学问题，解方程）；
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！