链表的基本操作：查找、删除

# 链表的基本操作：查找、删除

# 一、链表的查找

# 剑指 Offer 22. 链表中倒数第k个节点 (opens new window)

☀️☀️☀️☀️☀️☀️题解一：使用快慢指针，其中一个指针先移动K个位置

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        //快慢指针
        ListNode slow = head, fast = head;
        //fast指针先行k步（k-->0处理k过大问题）
        while(k-- > 0 && fast != null) fast = fast.next;
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13

# 876. 链表的中间结点 (opens new window)

☀️☀️☀️☀️☀️☀️题解一：

class Solution {
    public ListNode middleNode(ListNode head) {
        //快慢指针获取中间节点
        ListNode slow = head,fast = 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

# 二、链表的删除

# 剑指 Offer 18. 删除链表的节点 (opens new window)

☀️☀️☀️☀️☀️☀️题解一：使用双指针，注意处理边界数据

class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        //dummy处理边界问题
        ListNode dummy = new ListNode(-1,head);
        ListNode pre = dummy,cur = head;
        while (cur != null) {
            if(cur.val == val){
                pre.next= cur.next;
                break;
            }
            cur = cur.next;
            pre = pre.next;
        }
        return dummy.next;
    }
}

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

# 剑指 Offer II 021. 删除链表的倒数第 n 个结点 (opens new window)

☀️☀️☀️☀️☀️☀️题解一：使用双指针，需要一个dummy节点

public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(-1,head);//边界问题，设置一虚节点
        ListNode pre = dummy,cur = head;
        while(cur != null && n-- >0) cur = cur.next;
        while(cur != null){
            pre = pre.next;
            cur = cur.next;
        }
        pre.next = pre.next.next;
        return dummy.next;
    }

1
2
3
4
5
6
7
8
9
10
11

#链表

← 有趣的加密算法-Bcrypt 链表的高级操作：链表的反转、合并、拆分→