链表相关算法题详解

本文主要是介绍链表相关算法题详解，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

1、(LeetCode21)合并两个有序链表

　　链接：https://leetcode.cn/problems/merge-two-sorted-lists/

　　题目：将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

　　思路：这道题可以用递归来做，首先判断两个链表的首节点哪个比较小，小的作为新节点，然后剩余的部分重复这个函数实现。

　　代码实现：

 1 class Solution {
 2     public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
 3         if(l1 == null) return l2;
 4         if(l2 == null) return l1;
 5         if(l1.val < l2.val){
 6             l1.next = mergeTwoLists(l1.next,l2);
 7             return l1;
 8         }
 9         l2.next = mergeTwoLists(l1,l2.next);
10         return l2;
11     }
12 }

2、(LeetCode83)删除排序链表中的重复元素

　　链接：https://leetcode.cn/problems/remove-duplicates-from-sorted-list/

　　题目：给定一个已排序的链表的头head， 删除所有重复的元素，使每个元素只出现一次 。返回已排序的链表。

　　思路：同样地用递归，如果首节点和第二个节点的值相等，那么就返回第二个节点，剩余的部分操作相同。

　　代码实现：

1 class Solution {
2     public ListNode deleteDuplicates(ListNode head) {
3         if(head == null || head.next == null) return head;
4         head.next = deleteDuplicates(head.next);
5         return head.val == head.next.val?head.next:head;
6     }
7 }

3、(LeetCode141)环形链表

　　链接：https://leetcode.cn/problems/linked-list-cycle/

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

　　思路：定义两个指针，一个快指针，一个慢指针，快指针一次移动两个节点，慢指针一次移动一个节点，如果存在环的话，那么这两个指针肯定会相遇，如果不存在环的话，那么就会走到结尾的null。

　　代码实现：

 1 public class Solution {
 2     public boolean hasCycle(ListNode head) {
 3         if(head == null) return false;
 4         ListNode slowPtr = head,fastPtr = head;
 5         while(fastPtr.next != null && fastPtr.next.next != null){
 6             slowPtr = slowPtr.next;
 7             fastPtr = fastPtr.next.next;
 8             if(slowPtr == fastPtr){
 9                 return true;
10             }
11         }
12         return false;
13     }
14 }

4、(LeetCode142)环形链表II

　　链接：https://leetcode.cn/problems/linked-list-cycle-ii/

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

　　思路：这道题算是上道题的升级版了，只需要将上道题的代码简单做下改动就可以了。首先开始的时候添加一个标志位来判断链表是否有环，当快慢指针相遇时，标志位置为true，代表存在环。当环存在时，慢指针指向头结点，快指针速度和慢指针相同，那么两指针相遇的位置就是环的起始位置。可能有的人理解不了为什么两指针相遇就是起始位置，这里我跳出题目，举个例子就懂了。

 　　像左图那样在一个环形链表定义两个指针，一个快指针一个慢指针，在一个位置出发，那么肯定还会在这个位置相遇，如果说我要是像右图那样，起点提前了n个节点，那么相遇的位置也会离上次相遇的位置距离n个节点，这个时候我要是把慢指针放到开始的位置上，并且快指针的速度也和慢指针一样，那么他们肯定会在环的入环位置相遇。

　　代码实现：

 1 public class Solution {
 2     public ListNode detectCycle(ListNode head) {
 3         if(head == null) return null;
 4         ListNode slowPtr = head,fastPtr = head;
 5         boolean loopExists = false;
 6         while(fastPtr.next != null && fastPtr.next.next != null){
 7             slowPtr = slowPtr.next;
 8             fastPtr = fastPtr.next.next;
 9             if(slowPtr == fastPtr){
10                 loopExists = true;
11                 break;
12             }
13         }
14         if(loopExists){
15             slowPtr = head;
16             while(slowPtr != fastPtr){
17                 fastPtr = fastPtr.next;
18                 slowPtr = slowPtr.next;
19             }
20             return slowPtr;
21         }
22         return null;
23     }
24 }

5、(LeetCode160)相交链表

　　链接：https://leetcode.cn/problems/intersection-of-two-linked-lists/comments/

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

　　思路：分别在两个表头定义两个指针，对链表进行遍历，遍历结束移向另一个表的表头，直到两交点相等。看过代码的话，可能会有这样一个疑问，如果两个链表长度一样并且还无交点，会不会死循环？当然这个也是不会的，因为遍历到最后，两个指针都指向了null，这时候就会把null返回出去，也是符合条件的。

　　代码实现：

 1 public class Solution {
 2     public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
 3         if(headA == null || headB == null){
 4             return null;
 5         }
 6         ListNode pA = headA,pB = headB;
 7         while(pA != pB){
 8             pA = pA == null ? headB : pA.next;
 9             pB = pB == null ? headA : pB.next;
10         }
11         return pA;
12     }
13 }

6、(LeetCode206)反转链表

　　链接：https://leetcode.cn/problems/reverse-linked-list/

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

　　思路：这道题只需要循环将当前节点的next指向前一个节点就OK了，注意在第一个节点之前加null.

　　代码实现：

 1 class Solution {
 2     public ListNode reverseList(ListNode head) {
 3         ListNode preNode = null;
 4         ListNode curr = head;
 5         while(curr != null){
 6             ListNode next = curr.next;
 7             curr.next = preNode;
 8             preNode = curr;
 9             curr = next;
10         }
11         return preNode;
12     }
13 }

7、(LeetCode234)回文链表

　　链接：https://leetcode.cn/problems/palindrome-linked-list/

　　题目：给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

　　思路：先定义一个栈，将链表的节点值存入到栈中，存好了之后，用pop()方法弹出末项来和头结点的值进行比较，若不相等，则返回false，若遍历完成，返回true。

　　代码实现：

 1 class Solution {
 2     public boolean isPalindrome(ListNode head) {
 3         Stack<Integer> stack = new Stack<Integer>();
 4         ListNode cur = head;
 5         while(cur != null){
 6             stack.push(cur.val);
 7             cur = cur.next;
 8         }
 9         while(head != null){
10             if(stack.pop() != head.val){
11                 return false;
12             }
13             head = head.next;
14         }
15         return true;
16     }
17 }

这篇关于链表相关算法题详解的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！