数据结构：LinkedList与链表—面试题（三）

目录

1、移除链表元素

2、反转链表

3、链表的中间结点

4、返回倒数第k个结点

 5、合并两个有序链表

---

1、移除链表元素

习题链接https://leetcode.cn/problems/remove-linked-list-elements/description/

描述：给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val ==      val 的节点，并返回 新的头节点 。

这道题大家看着是不是十分的眼熟，这其实就是我们在讲解无头单向链表时进行的一个方法的模拟实现

首先这道题我们要先进行头节点的判断如果头节点为空就代表链表为空，没有数据直接返回null

如果不为空，我们要创建两个指针，一个指向头结点（prev）,一个指向头节点的下一个结点（cur）,然后让cur不断的往前走，在走的过程中进行判断，如果cur的值不等于我们要删除的值就让prev移动到目前cur的位置，之后cur继续走如果cur的值等于我们要删除的数，居然prev的后继结点变成此时cur的后继结点，以达到删除结点的目的

完整代码

class Solution {public ListNode removeElements(ListNode head, int val) {if(head == null){return null;}ListNode cur = head.next;ListNode perv = head;while(cur != null){if(cur.val == val){perv.next = cur.next;}else{perv = cur;}cur = cur.next;}if(head.val == val){head = head.next;}return head;}
}

2、反转链表

习题链接https://leetcode.cn/problems/reverse-linked-list/description/

描述：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

首先我们依然要进行头结点的判断，但是这次我们又加了一个判断因为我们这次是要将一个链表进行反转，而当我们的链表只有一个数时，进行反转后的链表依旧跟原来一样，因此当头节点的下一个为空时即链表只有一个数，就直接返回头结点即可。

然后这次我们依然要创建一个指针指向头结点的下一个结点（cur）,因为这次我们是反转链表我们的头节点将会变成最后一个结点，而最后有一个结点是没有后继结点的，因此我们要将头节点的后继置为空。

之后我们不断让cur往后走，并在循环中创建一个新的指向（curN）令他指向cur的下一个结点，这时我们让cur的下一个结点变成头节点，之后在将cur变成头节点，然后我们在让cur指针指向curN处，而进行新的循环时curN因为cur的改变会往后走一个结点这样就实现了cur的移动和链表的反转。

完整代码

class Solution {public ListNode reverseList(ListNode head) {if(head == null){return null;}if(head.next == null){return head;}ListNode cur = head.next;head.next = null;while(cur != null){ListNode curN =cur.next;cur.next = head;head = cur;cur = curN;}return head;}
}

3、链表的中间结点

习题链接https://leetcode.cn/problems/middle-of-the-linked-list/description/描述：给你单链表的头结点 head ，请你找出并返回链表的中间结点。如果有两个中间结点，则返            回第二个中间结点。

在这里我们用到了一个我们在做题时经常会使用到的一个方法：快慢指针。

所谓快慢指针其实就是让两个指针以同时移动但他们每次移动的距离是不同的这样就使得两个指针移动速度变得不同。

在这道题里我们使用的就是这种方法：首先我们设立两个指针，快指针（fast）和慢指针（slow）让他们指向头节点。

那么我们该怎样利用这两个指针找到中间结点呢?

我们来上面这两个事例，当这两个指针都在头节点时，我们让fast指针每次走两步，让slow指针每次走一步，当fast指针走到链表尽头时，即fast为空和fast的下一个结点为空时，结束移动，这时当我们结束移动后，会发现我们的slow指针正处于我们要找的中间结点位置

完整代码

class Solution {public ListNode middleNode(ListNode head) {ListNode fast = head;ListNode slow = head;while(fast != null && fast.next != null){fast = fast.next.next;slow = slow.next;}return slow;}
}

4、返回倒数第k个结点

习题链接https://leetcode.cn/problems/kth-node-from-end-of-list-lcci/description/

描述：实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。

对于这道题他让我们去求倒数第k个结点的值，在这里我们有一种方法来解决这个问题。

首先我们求出这个链表的长度，我们再用我们求出的长度减去k，这时根据得到的数，我们让一个指针从头结点走这个数的步，我们会发现最后停下的这个结点值正是倒数第k个结点的值。

完整代码

class Solution {public int kthToLast(ListNode head, int k) {ListNode cur = head;int count = 0;while(cur != null){count++;cur = cur.next;}ListNode fast = head;int n = count-k;while(n != 0){fast = fast.next;n--;}return fast.val;}
}

 5、合并两个有序链表

习题链接https://leetcode.cn/problems/merge-two-sorted-lists/description/描述：将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所             有节点组成的。

在这里我们用到了一个我们经常使用的方法：创建一个虚拟头结点 

在这道题里我们先创建一个虚拟头结点node，在创建一个指针tmp指向虚拟头结点

我们发现这道题的要求是将两个升序链表合并为一个新的 升序 链表，所以我们需要进行大小的比较，因此在这里我们先创建一个循环，在循环中进行比较，让list1链表的值小于list2时就让tmp的后继变成这时list1，然后让list1往后走，反之就让tmp的后继变成这时list2，然后让list2往后走，并且，每比较一次就让tmp往后走一步，这样就成功实现了大小的比较和，两个链表的合并，但是这里我们需要注意一点，如果有一个链表先走完了，我们就可以让另一个链表剩下的值直接链接在tmp后边。最后返回从虚拟头节点的下一个结点返回链表，这时的链表就是我们新的 升序 链表

完整代码 

class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode node = new ListNode(-1);ListNode tmp = node;while(list1 != null && list2 != null){if(list1.val < list2.val){tmp.next = list1;list1 = list1.next;}else{tmp.next = list2;list2 = list2.next;}tmp = tmp.next;}if(list1 == null){tmp.next = list2;}if(list2 == null){tmp.next = list1;}return node.next;}
}

6、分割链表

习题链接https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8&&tqId=11004&rp=2&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking描述：现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。

首先我们创建两个虚拟头结点，并用两个指针指向他们，根据题目意思我们要将所有小于x的数放到一边，大于等于的放到另一边，并且不改变他们的顺序，这样的话我们利用排序肯定是不可以了，因此我们利用了虚拟头节点的办法，我们将小于x的放到一个链表当中，大于等于x的放到另一个链表中，最后在让这两个链表链接在一起，这样就成功的分割了链表

注意：在最后我们要将存放大于等于x的链表最后一个结点的后继如果不等于空就要置为空。

           如果小于x 的链表为空，我们可以直接返回大于等于x的链表。

 

完整代码

public class Partition {public ListNode partition(ListNode pHead, int x) {ListNode head1 = new ListNode(-1);ListNode head2 = new ListNode(-2);ListNode cur = head1;ListNode prev = head2;ListNode node = pHead;while(node != null){if(node.val < x){cur.next = node;cur = cur.next;}else{prev.next = node;prev = prev.next;}node = node.next;}cur.next = head2.next;if(head2.next != null){prev.next = null;}if(head1.next == null){return head2.next;}return head1.next;}
}

7、链表的回文结构 

习题链接https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa?tpId=49&&tqId=29370&rp=1&ru=/activity/oj&qru=/ta/2016test/question-ranking

描述：对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。

根据题意我们直到我们要判断链表是否为回文链表，我们当为空和只有一个数时都是回文结构，因此要先进行判断，之后我直到回文结构代表链表一半和另一半的反转时相同的，因此我们发现这时我们上面讲的反转链表和求中间结点的结合，所以这题的思路就是找到中间结点，讲中间结点和之后的结点进行反转最后在与另一半进行比较每个结点的值如果出现一个不等就代表不是回文结构，如果另一个链表的下一个值，等于我们反转后最后一个值直接就可以范围true

完整代码

public class PalindromeList {public boolean chkPalindrome(ListNode A) {if(A == null || A.next ==null){return true;}ListNode fast = A;ListNode slow = A;while(fast != null && fast.next != null){fast = fast.next.next;slow = slow.next;}ListNode cur = slow.next;while(cur != null ){ListNode curN = cur.next;cur.next = slow;slow = cur;cur = curN;}while(A != slow){if(A.val != slow.val){return false;}if(A.next == slow){return true;}A = A.next;slow = slow.next;}return true;}
}

8、相交链表 

习题链接https://leetcode.cn/problems/intersection-of-two-linked-lists/

描述：给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。 

首先我们创建两个指针cur1和cur2，令他们分别指向head1和head2,这道题要我们判断两个链表存不存在相交结点，但是我们知道这两个可能长度是不相同的这就会导致在他们相交前是不一样长的因此，我们要先求出这两个链表的长度差，然后让长的链表先走差值步，令他们在同一个起跑线上，在一步一步的走，同时进行判断，如果走到最后都没有相等就代表没有相交

 

完整代码

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode cur1 = headA;ListNode cur2 = headB;int count1 = 0;while(cur1 != null){cur1 = cur1.next;count1++;}int count2 = 0;while(cur2 != null){cur2 = cur2.next;count2++;}cur1 = headA;cur2 = headB;int count3 = count1-count2;if(count3 < 0){cur1 = headB;cur2 = headA;count3 = count2 -count1;}while(count3 != 0){cur1 = cur1.next;count3--;}while(cur1 != cur2){cur1 = cur1.next;cur2 = cur2.next;}if(cur1 == null){//当走到最后链表会为空，但这时他们会相等，因此跳出循环，所以我们要先判 //断是否是走到尽头引起的相等，如果是就返回null,如果不是就往下执行truereturn null;}return cur1;}
}

9、环形链表 

习题链接https://leetcode.cn/problems/linked-list-cycle/description/描述：

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

这道题利用了快慢指针法，根据题意他要判断是否为环形链表，如果他是环形的话我们发现如果我们利用快慢指针，让一个指针一次走两步一个一次走一步，当慢指针进环的时候最好的情况下很快就会相遇，最坏的情况下是他们直接的距离是环的长度，但因为慢指针一次走一步快指针一次走两步，没动一次他们间的距离就会减少一步，因此他们一定会相遇，所以，如果他们相遇就代表有环，如果快指针走到最后为空就代表没有环

注意：当链表为空和只有一个结点时也是没有环的。

 

完整代码 

public class Solution {public boolean hasCycle(ListNode head) {if(head == null || head.next == null){return false;}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;}
}

10、环形链表II

 习题链接https://leetcode.cn/problems/linked-list-cycle-ii/description/

描述：

给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改链表。

这道题让我们去求环的入口点，首先我们来看下面这张图 

我们知道当我们进行环的判断时会有一个相遇点(M)，我们假设入口点(E)到相遇点的距离为x,环的总长为R, 而链表的头结点到入口点的距离为L，根据上题我们知道两个指针在相遇前快指针可能已经走了n圈，所以快指针走的路程为L+x+nR，慢指针走的路程为L+x，而快指针是以慢指针的2倍前进的，因此他们相遇时快指针的的路程是慢指针的两倍，因此我们得出2*（L+x）=L+x+nR

当我们化简后发现L= nR-x,而我们的n取决于fast走的圈数，但是当我们以n=1来看时，我们发现L的长度就等于R-X（L=R-x是一定的，n的形成只是由于指针速度不同所导致的），这时我们发现如果有两个指针从头节点和相遇点一起走当他们相遇时的相遇结点就是我们的入口点

 

 完整代码

public class Solution {public ListNode detectCycle(ListNode head) {if(head == null || head.next == null){return null;}ListNode fast = head;ListNode slow = head;while(fast != null && fast.next != null){fast = fast.next.next;slow = slow.next;if(fast == slow){break;}}if(fast == null || fast.next == null){return null;}fast = head;while(fast != slow){fast = fast.next;slow = slow.next;}return fast;}
}

---

好了今天的分享就到这里了，还请大家多多关注，我们下一篇见！