数据结构(Java版)第七期：LinkedList与链表(二)

专栏：数据结构(Java版)

个人主页：手握风云

一、链表的实现（补）

接上一期，下面我们要实现删除所有值为key的元素，这时候有的老铁就会想用我们上一期中讲到的remove方法，循环使用remove方法，去删除完值为key的元素。如下图所示，比如我们要删除值为22的节点，使用remove方法循环，此时这个算法的时间复杂度就会为 $O(n^{2})$ ，算法效率就会比较低。那我们能不能只让cur遍历一遍这个链表，就删除所有值为22的节点呢？

java">    @Overridepublic void removeAllKey(int key) {ListNode cur = head.next;ListNode prev = head;if(head == null){return;}while(cur != null){if(cur.val == key){prev.next = cur.next;}else{prev = cur;}cur = cur.next;}}

这样我们就可以实现删除所有职位key的元素，但我们要思考一下，这段代码的问题。我们来运行测试一下。

java">public class Main {public static void main(String[] args) {IList mySingleList = new MySingleList();mySingleList.addLast(22);mySingleList.addLast(22);mySingleList.addLast(22);mySingleList.addLast(33);mySingleList.display();mySingleList.removeAllKey(22);mySingleList.display();}
}

我们就会发现运行结果里面还有22。如下图所示，我们会看到，当cur走到第三个节点时，第二个22就会变成新的头，走得时候又会把新的22给忽略掉。我们可以这样解决这个问题。

java">    @Overridepublic void removeAllKey(int key) {ListNode cur = head.next;ListNode prev = head;if(head == null){return;}while(head.val == key){head = head.next;}while(cur != null){if(cur.val == key){prev.next = cur.next;}else{prev = cur;}cur = cur.next;}}

二、链表中经典的面试题

2.1. 反转链表

反转链表是将链表的结构进行反转，同时包括数据与地址。过程如下图所示。

对于这道题，我们可以采用头插的思想来解决。我们需要定义两个变量cur和curNext，利用以下代码来解决。我们先把head.next置为空，把cur方法到第二个节点上，然后把第二个节点采用头插的方法进行插入。可我们把cur改了之后，就会找不到下一个节点了，我们再定义一个curNext

java">while(cur != null){curNext = cur.next;cur.next = head;head = cur;cur = curNext;
}

2.2. 链表的中间结点

第一种方法，可以先求出链表长度，再定义一个引用，走到len/2的位置。但这种方法需要先定义cur节点去遍历一边数组得出链表的长度，再定义一个len变量走到中间节点的位置，这样就会需要遍历两遍链表。那我们能不能只遍历一遍数组得出中间节点。

类比一下，试想两个人赛跑，其中一人是另一个人速度的两倍，当速度快的到达终点时，速度慢的刚到达中点。同样，我们定义一个fast和slow两个引用变量。fast一次走两步，slow一次走一步。如果链表有奇数个结点时，当fast.next==null时，slow指向中间结点；如果链表有偶数个结点时，当fast==null时，slow指向中间结点。

java">public class Solution {static class ListNode{private int val;private Solution.ListNode next;public ListNode(Solution.ListNode next) {this.next = next;}public ListNode(int val, Solution.ListNode next) {this.val = val;this.next = next;}}public ListNode middleNode(ListNode head){if(head == null){return null;}ListNode fast = head;ListNode slow = head;while(fast != null && fast.next != null){
//这里不能是||，因为||无法到达链表的尾部
//两个条件的顺序不能互换，因为fast为空，fast.next就会空指针异常fast = fast.next.next;slow = slow.next;}return slow;}public static void main(String[] args) {ListNode node5 = new ListNode(5,null);ListNode node4 = new ListNode(4,node5);ListNode node3 = new ListNode(3,node4);ListNode node2 = new ListNode(2,node3);ListNode node1 = new ListNode(1,node2);Solution solution = new Solution();ListNode middleNode = solution.middleNode(node1);System.out.println(middleNode.val);}
}

2.3. 返回倒数第k个结点

我们依然可以参照上面的双引用的例子，先让slow不动，fast引用先走k-1步。然后两个引用在同时走。当fast走到最后的时候，slow就能走到倒数第k个结点。

java">public class Solution {static class ListNode{int val;ListNode next;public ListNode(){}public ListNode(int val) {this.val = val;}public ListNode(int val, ListNode next) {this.val = val;this.next = next;}}public int kthToLast(ListNode head, int k){ListNode fast = head;ListNode slow = head;int count = 0;while(count != k-1){fast = fast.next;count++;}while(fast.next != null){fast = fast.next;slow = slow.next;}return slow.val;}
}

这样的代码还不是特别严谨的。加入我们输入了5个结点，要求我们返回第6个结点，那我们的fast就需要走5步，直接指向了空指针，我们可以再写一个if语句来返回-1。或者是我们可以写成异常来接收，但在OJ测试上，异常不会通过。

java">if(fast == null){return -1;
}

以下为完整代码：

java">import java.util.Scanner;public class Solution {static class ListNode{int val;ListNode next;public ListNode(){}public ListNode(int val) {this.val = val;}public ListNode(int val, ListNode next) {this.val = val;this.next = next;}}public int kthToLast(ListNode head, int k){ListNode fast = head;ListNode slow = head;int count = 0;while(count != k-1){fast = fast.next;if(fast == null){return -1;}count++;}while(fast.next != null){fast = fast.next;slow = slow.next;}return slow.val;}public static void main(String[] args) {Scanner in = new Scanner(System.in);ListNode node5 = new ListNode(5,null);ListNode node4 = new ListNode(4,node5);ListNode node3 = new ListNode(3,node4);ListNode node2 = new ListNode(2,node3);ListNode node1 = new ListNode(1,node2);int k = in.nextInt();Solution solution = new Solution();int result = solution.kthToLast(node1,k);System.out.println(result);}
}

2.4. 合并两个有序链表

两个链表合并之后，要满足升序的条件，就需要对两个链表所指向的结点值进行比较，这就需要两个引用都不能为空。我们先定义一个傀儡结点newH，如上图所示，起初headA的val值比headB的val值小，那么headA就会指向下一个结点，再把0x23赋给我们的傀儡结点，再与headB的val值进行比较。那我们就可以写一个循环来对val进行比较。

我们还需要再定义一个ListNode.tmp，当headA走到下一个结点时，tmp走到上一个结点，这样就能保证刚进行比较的两个结点中最小的结点值是新创建链表的最后一个结点。

java">while(headA != null && headB != null){if(headA.val < headB.val){tmp.next = headA;headA = headA.next;tmp = tmp.next;} else {tmp.next = headB;headB = headB.next;tmp = tmp.next;}
}

在这个循环当中，一定会出现一种情况，其中一个链表先走完，而另一个链表还没有走完，此时先走完的链表已经指向空引用了，while循环就会跳出。我们利用下面的伪代码来遍历未完成的结点。

java">if(headA != null){tmp.next = headA;
} else {tmp.next = headB;
}

以下为完整代码：

java">public class Solution {static class ListNode{int val;ListNode next;public ListNode(){}public ListNode(int val) {this.val = val;}public ListNode(int val, ListNode next) {this.val = val;this.next = next;}}public ListNode mergeTwoLists(ListNode list1, ListNode list2){ListNode newH = new ListNode(-1);ListNode tmp = newH;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 = list1;} else {tmp.next = list2;}return newH.next;}public static void main(String[] args) {ListNode list1 = new ListNode(1);list1.next = new ListNode(2);list1.next.next = new ListNode(4);ListNode list2 = new ListNode(0);list2.next = new ListNode(3);list2.next.next = new ListNode(4);Solution solution = new Solution();ListNode mergedList = solution.mergeTwoLists(list1,list2);while (mergedList != null) {System.out.print(mergedList.val + " ");mergedList = mergedList.next;}}
}