160. 相交链表

题目描述

给定两个单链表的头节点 headA 和 headB , 请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点则返回空.

  • 数据保证整个链式结构中不存在环
  • 函数返回结果后, 链表必须保持其原始结构
  • 进阶考虑: 设计时间复杂度 O(m + n) , 空间复杂度 O(1) 的解决方案.

Solution

考虑双指针 pA-pB, 不妨考虑链表 $A$ 有 $m$ 个节点, 记为 $1\sim m$ , 链表 $B$ 有 $n$ 个节点, 记为 $1\sim n$

  1. 相交, 相交位置对于 $A$ 来说为 $a$ , 对 $B$ 来说是 $b$ , 则 $A$ 有 $a - 1$ 个不相交节点, $m - a + 1$ 个相交节点, $B$ 有 $b - 1$ 个不相交节点, 有 $n - b + 1$ 个相交节点. 又知道相交部分节点数量应该相同, 即 $m - a + 1 = n - b + 1$ , 整理得 $m + b = n + a$ , 左式的含义就是: pA 先走完链表 $A$ , 再从链表 $B$ 走到相交节点. 右式的含义是: pB 先走完链表 $B$ , 再从链表 $A$ 走到相交节点.
  2. 不相交, 先考虑 $m = n$ , 则会第一遍同时走到末尾同时为空指针. 再考虑 $m\ne n$ , pA 先走完链表 $A$ 再走完链表 $B$ , pB 先走完链表 $B$ 再走完链表 $A$ , 还是会同时到达空指针.

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/* 
 * language: C++
 * author: liuwx
 */
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *pA = headA;
        ListNode *pB = headB;
        while(pA != pB) {
            pA = (pA == nullptr ? headB : pA->next);
            pB = (pB == nullptr ? headA : pB->next);
        }
        return pA; 
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/* 
 * language: C#
 * author: liuwx
 */
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode GetIntersectionNode(ListNode headA, ListNode headB) {
        ListNode pA = headA;
        ListNode pB = headB;
        while(pA != pB) {
            pA = (pA == null ? headB : pA.next);
            pB = (pB == null ? headA : pB.next);
        }
        return pA;
    }
}

206. 反转链表

题目描述

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

Solution

模拟即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/* 
 * language: C++
 * author: liuwx
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *prev = nullptr;
        while(head != nullptr) {
            ListNode *nxt = head->next;
            head->next = prev;
            prev = head;
            head = nxt;
        }
        return prev;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/* 
 * language: C#
 * author: liuwx
 */
public class Solution {
    public ListNode ReverseList(ListNode head) {
        ListNode prev = null;
        while(head != null) {
            ListNode nxt = head.next;
            head.next = prev;
            prev = head;
            head = nxt;
        }
        return prev;
    }
}

234. 回文链表

给定链表判断是否属于回文链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        std::vector<int> num;
        while (head != nullptr) {
            num.push_back(head->val);
            head = head->next;
        }
        bool ok = true;
        for (int i = 0, j = (int)num.size() - 1; i < j; i ++, j --) {
            if(num[i] != num[j]) {
                ok = false;
                break;
            }
        }
        return ok;
    }
};

141. 环形链表

给定链表判断是否有环

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
const int value = 114514;
public:
    bool hasCycle(ListNode *head) {
        while(head != nullptr) {
            if(head->val == value) return true;
            head->val = value;
            head = head->next;
        }
        return false;
    }
};