链表(三)——链表中的经典算法

反转链表

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

思路：反转链表就是总体调整方向，这时候只需遍历一遍链表，注意，开始时，cur在head位置，prev为cur位置的前一个结点，开始时为空，首先需要设置一个保留下一个结点地址的curNext，此时cur位置的指向就可以改变成相反方向prev位置，然后cur走到curNext位置，以cur不为空进行循环，就可以达到翻转的目的

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode cur=head;
        ListNode prev = null;
        
        //保存下一个结点
        while(cur!=null){
        ListNode curNext = cur.next;
        cur.next=prev;
        prev=cur;
        cur=curNext;
        }
        return prev;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

链表的中间结点

给定一个头结点为 head 的非空单链表，返回链表的中间结点。 如果有两个中间结点，则返回第二个中间结点。 输入：[1,2,3,4,5] 输出：此列表中的结点 3
输入：[1,2,3,4,5,6] 输出：此列表中的结点 4

思路：找到中间结点，比较简单，运用快慢指针，快的结点一次性走两步，慢的一次性走一步，最终快指针fast到达空指针位置或者fast.next到空指针的位置，循环停止，这时候满指针flow走的距离就是快指针的一般，对应的位置就是中间结点

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast!=null&&fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
        }
        return slow;
    }
}
1
2
3
4
5
6
7
8
9
10
11

链表的回文结构

对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。

给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。
测试样例：1->2->2->1 返回：true

思路：回文链表面试中比较常见，其最优解法就是运用前面两道题的思想，并结合起来，先用快慢指针的方法，找到中间的位置，再将后面的序列与之倒序,此时slow就是这个链表的尾端，通过尾端和首端，都相向移动，如果相遇，则是回文链表，如果过程中，不相等，两边的值，则不是回文链表。还需判断特殊情况，当链表长度为偶数，可以通过相邻时，某个链表的next.val是否等于当前的val；

public class PalindromeList {
    public boolean chkPalindrome(ListNode A) {
        //判断是否为回文链表，首先找到中间值
        if(A == null)return false;
        if(A.next == null)return true;
        ListNode fast = A;
        ListNode slow = A;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next; 
        }
        //此时slow就是中间值，然后反转后面的结点
        ListNode cur = slow;
        ListNode nextNode = null;
        while(cur != null){
            nextNode = cur.next;
            cur.next = slow;
            slow = cur;
            cur = nextNode;
        }
        while(slow != A){
            if(slow.val != A.val){
                return false;
            }
            slow=slow.next;
            A = A.next;
            //判断偶数
            if(A.next==slow && A.val==slow.val){
                return true;
            }
        }
        return true;  
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

思路：合并两个有序列表成新的链表，则此时可以创建一个链表，通过比较合并前的两个链表的val值，判断大小，小的先放进新的链表中，最终新的链表就是完全时有序的链表。当一个链表为空时，那新的链表只需要将最后一个结点的next值与另一个链表连接起来，就完成了合并两个链表。

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
       
        ListNode newHead = new ListNode(1);
        ListNode temp = newHead;
        while(list1 != null && list2 != null){
        if(list1.val

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27

链表中倒数第k个结点

输入一个链表，输出该链表中倒数第k个结点。
输入：{1,2,3,4,5},1
返回值：{5}

思路：这道题还是可以借助快慢指针来解决，这倒数k个结点，就相当于快的指针夺走了k-1步，如果快的真正fast.next为null，此时的slow就是慢指针的位置就是倒数第k个结点

public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
 
        if(k <= 0)
            return null;
        ListNode low = head;
        ListNode fast = head;
        for(int i=1; i < k;i++){
            if(fast == null)
                return null;
            else
                fast = fast.next;
        }
        if(fast == null)
            return null;
        while(fast.next != null){
            low = low.next;
            fast = fast.next;
        }
        return low;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5]
输出：Intersected at ‘8’

思路：两个结点相交，则后续的结点是重合的，也就是说它们公用这几个结点，这两个链表的长度只差的绝对值，就是解题的关键，这时候求出长度差后，只需要让长链表先走长度差的距离，最后两个链表同时遍历，每一次走过一个结点，相遇的结点，就是要找的相交结点。如果遍历完，两者的指向还是不相等，则不存在相交结点，此时返回空结点null。

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if((headA == null) || (headB == null)) return null;
        //先求出链表长度的差值
         int lengthSub = length(headA)-length(headB);
         if(lengthSub<0){
             lengthSub=-lengthSub;
         }

        //假设headA链表长度要长一些
        if(length(headA) > length(headB)){
            for(int i=0;i

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41
• 42

链表分割

现有一链表的头结点pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。

思路：给出了分界值，大体思路只需要创建两个链表，如果给出的pHead链表上的结点val值小于x值，则放在前面一个链表，反之放在后面一个链表，最后两个链表进行拼接，就形成了一个新的链表，就是重新排序后的链表。但是最后需要将第二个链表置为空，防止形成环。

public class Partition {
    public ListNode partition(ListNode Head, int x) {
        if(Head==null){
            return null;
        }
        ListNode firstStare= null;
        ListNode firstEnd= null;
        ListNode laterStare= null;
        ListNode laterEnd= null;
        ListNode cur=Head;
        while(cur != null){
            if(cur.val < x ){
                if(firstStare == null){
                    firstStare = cur;
                    firstEnd = cur;
                    cur = cur.next;
                }else{
                    firstEnd.next = cur;
                    firstEnd = cur;
                    cur = cur.next;
                }
                
            }else{
                if(laterStare == null){
                    laterStare = cur;
                    laterEnd = cur;
                    cur = cur.next;
                }else{
                    laterEnd.next = cur;
                    laterEnd = cur;
                    cur = cur.next;
                }
                
            }
        }
        if(firstStare == null){
            return laterStare;
        }
        if(laterEnd != null){
            laterEnd.next = null;
        }
        firstEnd.next = laterStare;
        return firstStare;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

环形链表

给定一个链表，判断链表中是否有环

快慢指针，即慢指针一次走一步，快指针一次走两步，两个指针从链表其实位置开始运行，如果链表带环则一定会在环中相遇，否则快指针率先走到链表的末尾。如果相遇，就代表形成了一个环。快指针一次性可以走三步，四步吗？答案是，不能！因为可能会出现特殊情况，当慢指针走一步，快指针走三步，这时候两个指针永远也不会相遇，即使是一个环形链表。

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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

环形链表 II

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

思路：让一个指针从链表起始位置开始遍历链表，同时让一个指针从判环时相遇点的位置开始绕环运行，两个指针都是每次均走一步，最终肯定会在入口点的位置相遇

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20