跳转至

移除链表元素 & 设计链表 & 反转链表

约 122 个字 148 行代码 预计阅读时间 2 分钟

Abstract

掌握画图进行分析以及常见的题型方法

链表的定义:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
public class ListNode {
    int val;
    ListNode next;
    public ListNode() {} //无参构造函数
    public ListNode(int val) { this. val = val; }
    public ListNode(int val, int next) {
        this.val = val;
        this.next = next;
    }
}

1
2
3
4
5
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {} // 构造函数
}

203.移除链表元素

1、两种情况: case1删除的是头，case2删除的非头

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        while(head != null && head.val == val) {
            head = head.next;
        } 
        ListNode cur = head;
        while(cur != null && cur.next != null) {
            if(cur.next.val == val) cur.next = cur.next.next;
            else cur = cur.next;
        }
        return head;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
ListNode* removeElements(ListNode* head, int val) {
    // case1
    while (head != nullptr && head->val == val) {
        ListNode* tmp = head;
        head = head->next;
        delete tmp;
    }
    // case2
    ListNode* cur = head;
    while (cur != nullptr && cur->next != nullptr) {
        if (cur->next->val == val) {
            ListNode* tmp = cur->next;
            cur->next = cur->next->next;
            delete tmp;
        } else {
            cur = cur->next;
        }
    }
    return head;
}

2、利用 虚拟头节点dummy 统一操作

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummy = new ListNode();
        dummy.next = head;
        ListNode cur = dummy;
        while(cur.next != null) {
            if(cur.next.val == val) cur.next = cur.next.next;
            else cur = cur.next;
        }
        return dummy.next;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
ListNode* removeElements(ListNode* head, int val) {
    ListNode* dummy = new ListNode(0);
    dummy->next = head;
    ListNode* cur = dummy;
    while (cur->next != nullptr) {
        if (cur->next->val == val) {
            ListNode* tmp = cur->next;
            cur->next = tmp->next;
            delete tmp;
        } else {
            cur = cur->next;
        }
    }
    head = dummy->next;
    delete dummy;
    return head;
}

707.设计链表

单链表的增删

利用虚拟头节点 → Ref

 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
46
47
48
49
class ListNode {
    int val;
    ListNode next;
    ListNode() { }
    ListNode(int val) { this.val = val; }
}
class MyLinkedList {
    int size;
    ListNode head;
    public MyLinkedList() {
        size = 0;
        head = new ListNode(0); //虚拟头节点       
    }
    public int get(int index) {
        if(index < 0 || index >= size) return -1;
        ListNode cur = head;
        for(int i = 0; i <= index; i ++) cur = cur.next;
        return cur.val;
    }
    public void addAtHead(int val) {
        ListNode newNode = new ListNode(val);
        newNode.next = head.next;
        head.next = newNode;
        size ++;
    }
    public void addAtTail(int val) {
        ListNode newNode = new ListNode(val);
        ListNode cur = head;
        while(cur.next != null) cur = cur.next;
        cur.next = newNode;
        size ++;
    }
    public void addAtIndex(int index, int val) {
        if(index > size) return;
        ListNode newNode = new ListNode(val);
        ListNode pre = head;
        for(int i = 0; i < index; i ++) pre = pre.next;
        newNode.next = pre.next;
        pre.next = newNode;
        size ++;
    }
    public void deleteAtIndex(int index) {
        if(index < 0 || index >= size) return;
        ListNode pre = head;
        for(int i = 0; i < index; i ++) pre = pre.next;
        pre.next = pre.next.next;
        size --;
    }
}

206.反转链表

每次维护相邻的指针，完成反向，继续向后走

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode pre = null, cur = head;
        while(cur != null) {
            ListNode next = cur.next;
            cur.next = pre; pre = cur; cur = next;
        }
        return pre;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
ListNode* reverseList(ListNode* head) {
    if (!head || !head->next) return head;
    ListNode* pre = nullptr, *cur = head;
    while(cur) {
        ListNode* next = cur->next;
        cur->next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
}

颜色主题调整

快来和我聊天~

可以的话请给我赞和 star喔~    =>  GitHub stars

评论