Leetcode算法（二）-探索初级算法-链表

发表于 | 分类于 ，

1. 概述

2. 算法题

2.1 删除链表中的节点

  • 请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点，你将只被给定要求被删除的节点
  • 解题思路
    • 很简单，直接将待删除结点的上一个结点指向待删除结点的下一个结点即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void deleteNode(ListNode* node) {
        node->val = node->next->val;
        node->next = node->next->next;
    }
};

2.2 删除链表的倒数第N个节点

  • 给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点
  • 解题思路
    • 双指针，一个提前走n+1步，第二个再与第一个一同前进，指导第一个走到尾，那么第二个指针所指向的结点的下一个结点就是要删除的节点
    • 注意要新建立头结点，因为头结点也有可能被删除
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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if(!head)  return head;
        ListNode *newHead = new ListNode(-1);
        newHead->next = head;
        ListNode *p = newHead, *q = newHead, *temp;
        int i = 0;
        while (q->next != NULL) {
            q = q->next;
            if (i >= n) {
                p = p->next;
            }
            i ++;
        }
        temp = p->next;
        p->next = p->next->next;
        delete temp;
        return newHead->next;
    }
};

2.3 反转链表

  • 反转一个单链表
  • 解题思路
    • 双指针思想
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* q = NULL, *p = head;
        while (p != NULL) {
            ListNode* m = p->next;
            p->next = q;
            q = p;
            p = m;
        }
        return q;
    }
};

2.4 合并两个有序链表

  • 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的
  • 解题思路
    • 迭代
    • 递归
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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode *newList = new ListNode(-1);
        ListNode *p = newList;
        while (l1 != NULL && l2 != NULL) {
            if (l1->val <= l2->val) {
                p->next = l1;
                l1 = l1->next;
            } else {
                p->next = l2;
                l2 = l2->next;
            }
            p = p->next;
        }
        p->next = l1 == NULL ? l2: l1;
        return newList->next;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        else if (l2 == null) {
            return l1;
        }
        else if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        }
        else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }

    }
}

2.5 回文链表

  • 请判断一个链表是否为回文链表
  • 解题思路
    • 双指针+反转
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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if (head == NULL || head->next == NULL) {
            return true;
        }
        ListNode *fast = head, *slow = head;
        ListNode *p, *pre = NULL;
        while (fast && fast->next) {
            p = slow;
            fast = fast->next->next;
            slow = slow->next;
            p->next = pre;
            pre = p;
        }
        if (fast) {
            slow = slow->next;
        }
        while (p) {
            if (p->val != slow->val) {
                return false;
            }
            p = p->next;
            slow = slow->next;
        }
        return true;
        
    }
};

2.6 环形链表

  • 给定一个链表，判断链表中是否有环
  • 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环
  • 解题思路
    • 双指针
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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (!head || !head->next) {
            return false;
        }
        ListNode *fast = head, *slow = head;
        while (fast && fast->next) {
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow) {
                return true;
            }
        }
        return false;
    }
};