Java链表试题详解（超全常见题型）

目录

1. 移除链表元素

2. 翻转/逆置链表

2.1 头插法

2.2 三指针法

3. 链表的中间结点

4. 链表中倒数第k个结点

5. 合并两个有序链表

6. 链表分割

7.  删除链表中重复的结点⭐⭐⭐

8. 链表的回文结构⭐⭐⭐

9. 相交链表

10. 环形链表⭐⭐

11. 环形链表Ⅱ⭐⭐⭐

1. 移除链表元素⭐

203. 移除链表元素 - 力扣（LeetCode） (leetcode-cn.com)

思路：定义前驱prev和cur，循环完再判断头结点

伪代码：

  1. 判断链表是否为空
  2. 定义两个结点prev和cur，循环进行替换
  3. 判断头结点是否为要删除的元素
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if (head == null) {
            return null;
        }
        ListNode prev = head;
        ListNode cur = head.next;
        while(cur != null) {
            if (cur.val == val) {
                prev.next = cur.next;
                cur = cur.next;
            } else {
                prev = cur;
                cur = cur.next;
            }
        }
        if (head.val == val) {
            head = head.next;
        }
        return head;
    }
}

2. 翻转/逆置链表⭐

206. 反转链表 - 力扣（LeetCode） (leetcode-cn.com)

2.1 头插法

思路：newHead新头结点、cur当前结点

curNext当前结点的下一跳（用于带领cur遍历）

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

2.2 三指针法

思路：cur当前结点，prev前驱，newHead新头结点，curNext为nur.next

当cur.next为空时，说明到表尾了，则将当前cur赋给newHead头结点

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

3. 链表的中间结点⭐

876. 链表的中间结点 - 力扣（LeetCode） (leetcode-cn.com)

给定一个头结点为 head 的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

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

4. 链表中倒数第k个结点⭐

链表中倒数第k个结点_牛客题霸_牛客网 (nowcoder.com)

输入一个链表，输出该链表中倒数第k个结点。

思路：快慢指针，快指针先走k-1次，然后快慢指针同时走，当快指针到底链尾时输出慢指针。

public class Solution {
    public ListNode FindKthToTail(ListNode head, int k) {
        if (head == null) return head;
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null) {
            if(k <= 0) {
                slow = slow.next;
            }
            fast = fast.next;
            k--;
        }
        return k<=0?slow:null;
    }
}

5. 合并两个有序链表⭐

21. 合并两个有序链表 - 力扣（LeetCode） (leetcode-cn.com)

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

思路：傀儡头结点newHead，cur用于给新的链表添加元素

注意在定义newHead时为其添加一个无效val，然后使cur=newHead ;

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

6. 链表分割⭐

链表分割_牛客题霸_牛客网 (nowcoder.com)

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

思路：定义cur遍历现有链表，定义newHead1，cur1为小于x的新链表1；定义newHead2，cur2为其他的新链表2；最后将两个链表连起来

注意：最后判断newHead1或2为空的情况，将尾结点置空。

public class Partition {
    public ListNode partition(ListNode pHead, int x) {
        if (pHead == null) return null;
        ListNode cur = pHead;
        ListNode newHead1 = null;
        ListNode cur1 = null;
        ListNode newHead2 = null;
        ListNode cur2 = null;
        while (cur != null) {
            if (cur.val < x ) {
                //第一次插入
                if (newHead1 == null) {
                    newHead1 = cur;
                    cur1 = cur;
                } else {
                    cur1.next = cur;
                    cur1 = cur1.next;
                }
            } else {
                if (newHead2 == null) {
                    newHead2 = cur;
                    cur2 = cur;
                } else {
                cur2.next = cur;
                cur2 = cur2.next;
                }
            }
            cur = cur.next;
        }
        if (newHead1 == null) {
            return newHead2;
        }
        cur1.next = newHead2;
        if (newHead2 != null) {
            cur2.next = null;
        }
        return newHead1;
    }
}

7.  删除链表中重复的结点⭐⭐⭐

删除链表中重复的结点_牛客题霸_牛客网 (nowcoder.com)

一个有序链表，删除该链表中重复的结点，重复的结点不保留，返回链表头指针。

思路：定义一个傀儡头结点和其指针，遍历cur原链表指针，最后注意手动将傀儡结点指针的next置空，返回newHead.next

public class Solution {
    public ListNode deleteDuplication(ListNode pHead) {
        if (pHead == null || pHead.next == null) return pHead;
        ListNode newHead = new ListNode(-1);
        ListNode newcur = newHead;
        ListNode cur = pHead;
        while (cur != null) {
            //cur.next!=null 用于保证cur不是尾巴结点
            if(cur.next != null && cur.val == cur.next.val) {
                while (cur.next != null && cur.val == cur.next.val) {
                    cur = cur.next;
                }
            } else {
                newcur.next = cur;
                newcur = newcur.next;
            }
            cur = cur.next;
        }
        newcur.next = null;    //手动设置，防止最后一个结点是重复的
        return newHead.next;
    }
}

8. 链表的回文结构⭐⭐⭐

链表的回文结构_牛客题霸_牛客网 (nowcoder.com)

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

给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。

思路：

  1. 找到中间结点（快慢指针）
  2. 反转链表后半部分
  3. 一前一后判断（只要不相等就返回false）

法一：

进行翻转时使用头插法，创建新的半段的头结点，保持中间结点slow位置不动

public class PalindromeList {
    public boolean chkPalindrome(ListNode A) {
        if (A == null || A.next == null) return true;
        ListNode fast = A;
        ListNode slow = A;
        //1、找中间结点，用slow定位到中间结点
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        //2、翻转，翻转后半段链表
        ListNode B = null;
        ListNode cur = slow;
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = B;
            B = cur;
            cur = curNext;
        }
        //3、判断
        while (A.next != slow) {
            if(A.val != B.val) {
                return false;
            }
            A = A.next;
            B = B.next;
        }
        return true;
    }
}

法二：

翻转时不新建结点，直接使用slow往后移动，注意：判断时考虑偶数（head.next==slow）情况

public class PalindromeList {
    public boolean chkPalindrome(ListNode A) {
        if (A == null || A.next == null) return true;
        //1、找到中间结点
        ListNode fast = A;
        ListNode slow = A;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        //2、翻转
        ListNode cur = slow.next;
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }
        //3、判断
        while (A != slow) {
            if (A.val != slow.val) {
                return false;
            }
            if (A.next == slow) {
                return true;
            }
            A = A.next;
            slow = slow.next;
        }
        return true;
    }
}

9. 相交链表⭐

160. 相交链表 - 力扣（LeetCode） (leetcode-cn.com)

找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

思路：

  1. 分别计算出两个链表的长度（定义方法求）
  2. 长的那一个链表先走差值的距离
  3. 然后一起走，看是否出现相等

法一：

public class Solution {
    public int getLength(ListNode head) {
        int count = 0;
        while (head != null) {
            count++;
            head = head.next;
        }
        return count;
    }
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
        int la = getLength(headA);
        int lb = getLength(headB);
        int x = la -lb;
        if( x > 0) {
            for (int i = 0; i < x; i++) {
                headA = headA.next;
            }
        } else if (x < 0) {
            for (int i = 0; i < -x; i++) {
            headB = headB.next;
            }
        }
        //也可以只判断两值是否相等，如果没有相交headA==headB==null
        while (headA != null && headB != null &&headA != headB) {
            headA = headA.next;
            headB = headB.next;
        }
        if (headA == headB) return headA;
        else return null;
    }
}

法二：

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
        int lenA = 0;
        int lenB = 0;
        //pl代表较长链表的长度，ps代表较短链表的长度
        ListNode pl = headA;
        ListNode ps = headB;
        while (pl != null) {
            lenA++;
            pl = pl.next;
        }
        while (ps != null) {
            lenB++;
            ps = ps.next;
        }
        //计算完长度恢复指针位置
        pl = headA;
        ps = headB;
        //求两链表长度的差值
        int len = lenA - lenB;
        if (len < 0) {
            pl = headB;
            ps = headA;
            len = lenB - lenA;
        }
        //长链表先走他们的差值次
        while (len != 0) {
            pl = pl.next;
            len--;
        }
        while (pl != ps) {
            pl = pl.next;
            ps = ps.next;
        }
        //这里的判断可以不写，因为假定没有相交，那么pl和ps也均为nul
        if (pl == null && ps == null) {
            return null;
        }
        return pl;
    }
}

10. 环形链表⭐⭐

141. 环形链表 - 力扣（LeetCode） (leetcode-cn.com)

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

思路：fast一次走两步，slow一次走一步，看会不会相遇

法一：

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

法二：

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) {
                break;
            }
        }
        if (fast == null || fast.next == null) {
            return false;
        }
        return true;
    }
}

11. 环形链表Ⅱ⭐⭐⭐

142. 环形链表 II - 力扣（LeetCode） (leetcode-cn.com)

如果链表有环，返回开始入环的第一个结点，否则返回null。

思路：假设环的长度为C，表头到入口点距离为X，相遇点到入口点为Y。

fast的路程为（X+C+C-Y），slow的路程为（X+C-Y），fast=2slow，解得X==Y

 即：在相遇以后，将slow置于表头，slow和fast以相同步长前进，再次相遇时，slow的位置即入口点

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) {
                break;
            }
        }
        if (fast == null || fast.next == null) return null;
        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}

版权声明：本文为qq_52057693原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。