3、单链表OJ题深度解剖
这个才是今天的重头戏，不是篮球哥不画图，是因为前面的图太简单了，小伙伴们结合着代码也能自己画出来，但是，对于OJ题，大家伙下去还是得画图的，相信看完这几道题，你会爱上数据结构的。
3.1 移除链表元素(来源:LeetCode 难度:简单)
题目：给你一个链表的头节点
head和一个整数val，请你删除链表中所有满足Node.val == val的节点，并返回 新的头节点 。
这个题我们可以用前后指针的思路来做，这样也比较通俗易懂，更适合初学者，大概的思路是这样的：我们可以定义一个cur和first的引用，如果碰到相等，也就是first.val == val，我们则让cur的next指向first的下一个节点，如果不相等，则让cur走到first的位置，最后first往后走一步，图解：
这里还没有完，如果第一个节点的值也是val呢？所以最后我们别忘了进行一个判断，那么最终的代码是这样的：
public ListNode removeElements(ListNode head, int val) { if (head == null) { return null; } ListNode cur = head; ListNode first = head; while (first != null) { if (first.val == val) { cur.next = first.next; } else { cur = first; } first = first.next; } // 判断头节点的值是否也是val if (head.val == val) { head = head.next; } return head; }
3.2 反转链表(来源:LeetCode 难度:简单)
题目：给你单链表的头节点
head，请你反转链表，并返回反转后的链表。
这个题我们可以先取到头节点，后续的节点都进行头插法即可？我们取到头节点，并且先将头节点的next置空，但是这样一来，就找不到后面的节点了，所以我们还需要有一个curNext引用来记录要反转节点的下一个节点：
我们的思路是这样的：首先找到头节点的next置空，cur走到curNext位置，curNext往前走，使得cur位置的next指向头节点，头节点cur再次成为新的头节点，当curNext走到null的时候循环结束。
public ListNode reverseList(ListNode head) { // 空链表的情况 if (head == null) { return null; } ListNode cur = head; ListNode curNext = cur.next; head.next = null; while (curNext != null) { cur = curNext; curNext = curNext.next; cur.next = head; head = cur; } return head; }
3.4 链表中倒数第k个节点(来源:牛客网 难度:简单)
题目：输入一个链表，输出该链表中倒数第k个结点。
这个题也是很简单的一道题，可以采用前后指针法，先让first指针走k步，走完之后slow和first一起走，这样slow和first之间就相差了k步，当first为null时，slow就是倒数第k个节点，在这个过程中，我们还要判断k的合法性，如果k小于等于0？或者k大于链表的长度呢？于是我们就能写出如下的代码：
public ListNode FindKthToTail(ListNode head,int k) { // 判断k的合法性 if (k <= 0 || head == null) { return null; } ListNode first = head; ListNode slow = head; // 先让first走k步 while (k != 0) { // k的长度大于链表的长度 if (first == null) { return null; } first = first.next; k--; } // 一起走,当first为null,slow就是倒数第k个节点 while (first != null) { first = first.next; slow = slow.next; } return slow; }
3.6 链表分割(来源:牛客网 难度:较难)
题目：现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
这个题的思路我们可以这样做，既然是按照给定的值x进行分割，那么我们设定两个盘子，盘子A放小于x的节点，盘子B放大于x的节点，最后把这两个盘子的节点连起来，放回盘子A的头节点即可！
public ListNode partition(ListNode pHead, int x) { if (pHead == null) { return null; } ListNode headA = null; ListNode headB = null; ListNode curA = null; ListNode curB = null; ListNode cur = pHead; while (cur != null) { if (cur.val < x) { // 第一次放入A盘子 if (headA == null) { headA = cur; curA = cur; } else { curA.next = cur; curA = cur; } } else { // 第一次放入B盘子 if (headB == null) { headB = cur; curB = cur; } else { curB.next = cur; curB = cur; } } cur = cur.next; } // 如果A盘子为空 if (headA == null) { return headB; } curA.next = headB; // 避免B盘子尾节点形成环 if (headB != null) { curB.next = null; } return headA; }
3.7 链表的回文结构(来源:LeetCode 难度:较难)
题目：对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。
给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。
这个题有要求的，要求空间复杂度为O(1)，并且还得在O(n)的时间复杂度下，那我们就原地解决这个题，我们可以分为三个步骤，首先找到中间节点，然后把中间节点往后的节点进行反转，最后左右两个指针同时往中间走。如果光看下面代码看不懂，可以结合着代码画图才能理解更透彻哦！
public boolean chkPalindrome(ListNode A) { if (A == null) { return false; } // 只有一个节点的情况 if (A.next == null) { return true; } // 首先找到中间节点 ListNode first = A; ListNode slow = A; while (first != null && first.next != null) { first = first.next.next; slow = slow.next; } // 走到这,slow是链表的中间节点,采用头插法反转slow后续的节点 first = slow.next; ListNode cur = slow; while (first != null) { cur = first; first = first.next; cur.next = slow; //链接前一个节点 slow = cur; //更新头节点的位置 } // 走到这,反转完毕,cur指向最后一个节点,让slow等于A,往中间找 slow = A; while (slow != cur) { if (slow.val != cur.val) { return false; } // 偶数的情况下需要特殊判断 if (slow.next == cur) { return true; } slow = slow.next; cur = cur.next; } return true; }
3.8 相交链表(来源:LeetCode 难度:简单)
题目：给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
这个题我们可以这样做，长链表先走两个链表的长度差的步数，因为相交之后的节点都是一样的个数，所以走了差值后，就两个链表一起往后走，相等了则就是相交节点。
public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if (headA == null || headB == null) { return null; } ListNode longList = headA; //longList始终记录长的链表 ListNode shortList = headB; // 分别求出两个链表的长度 int lenA = 0; int lenB = 0; ListNode cur = headA; while (cur != null) { lenA++; cur = cur.next; } cur = headB; while (cur != null) { lenB++; cur = cur.next; } int len = lenA - lenB; // 如果B链表长于A链表 if (len < 0) { // 修正相差长度 len = lenB - lenA; longList = headB; //longList始终记录长的链表 shortList = headA; } // 让长链表先走差值len步,然后同步走,相等了即为相交节点 while (len != 0) { longList = longList.next; len--; } while (longList != shortList) { longList = longList.next; shortList = shortList.next; } // 如果两个链表走到了null,则没有中间节点返回null,如果有,返回任意一个即可 return longList; }
