Linked List 介绍

资料来源《程序员面试金典》第九章

链表是由一些列节点(node)组成的数据结构，每个节点拥有指向下一个节点的指针(双向链表中，每一个节点同时拥有指向上一个节点和下一个节点的指针)。

单链表：

单链表

双链表：

双链表

链表的好处是可以在常数的时间添加和删除元素，在特定的情况下特别有用。和数组不同的是，链表无法在常数时间复杂度内访问链表的一个特定索引，如果想要访问第N个元素，就需要迭代访问N次。

Node数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Node<T>{
    public T Data { set; get;}
    public Node<T> Next { set; get;}
    
    public Node(T val){
        this.Data = val;
        this.Next = null;
    }
    
    public Node(){
        this.Data = default(T);
        this.Next = null;
    }
}

LinkedList数据结构

1
2
3
4
5
6
7
public class LinkedList<T>{
    public Node<T> header { set; get;}
    
    public LinkedList(){
        this.header = null;
    }
}

Linked List 习题

例题1

《程序员面试金典》第九章2.4

编写程序以 x 为基准分割链表，使得所有小于 x 的节点排在大于或等于 x 的节点之前。如果链表中包含 x，x 只需出现在小于 x 的元素之后(如下所示)。分割元素 x 只需处于“右半部分”即可，其不需要被置于左右两部分之间。

示例:

1
2
输入: head = 3->5->8->5->10->2->1, x = 5
输出: 3->1->2->10->5->5->8

思路

使用头插法，将碰到的小于x的节点直接插入到链表头的前面

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public ListNode Partition(ListNode head, int x) {
        if (head == null) return null;
        ListNode shadow = head;
        while (shadow.next!= null)
        {
            if (shadow.next.val < x)
            {
                ListNode temp = shadow.next;
                shadow.next = temp.next;
                temp.next = head;
                head = temp;
            }
            else
            {
                shadow = shadow.next;
            }
        }

        return head;
}

例题2

《程序员面试金典》第九章2.8

给定一个链表，如果它是有环链表，实现一个算法返回环路的开头节点。
有环链表的定义：在链表中某个节点的next元素指向在它前面出现过的节点，则表明该链表存在环路。

示例 1：

1
2
3
输入：head = [3,2,0,-4], pos = 1
输出：tail connects to node index 1
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

1
2
3
输入：head = [1,2], pos = 0
输出：tail connects to node index 0
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

1
2
3
输入：head = [1], pos = -1
输出：no cycle
解释：链表中没有环。

思路

环路检测

使用“快行指针”进行求解，假设一个慢指针一次走一步，一个快指针一次走两步，如果链表有环，那么快指针和慢指针肯定会相遇。

  • x: 链表起点
  • y: 环的起点
  • A: 链表起点到环的起点的长度
  • B: 环的起点到两个指针相遇的位置的长度

到相遇点为止，慢指针走过了距离 s1 = A + B, 快指针走过了 s2 = A + B + N * (环路长度)， 也就是说快指针走了N圈和慢指针相遇了。又因为快指针一次走两步，慢指针一次走一步，所以快指针走过的距离s2是慢指针走过的距离s1的两倍：2*s1 = s2，得到 2( A + B ) = A + B + N * (环路长度)。我们需要求 y 的位置，也就是计算A的长度。简化得到 A = N * (环路长度) - B

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
public ListNode DetectCycle(ListNode head)
{
    ListNode slow = head;
    ListNode fast = head;
			
    // 找到相遇点
    while (fast != null && fast.next!=null)
    {
        slow = slow.next;
        fast = fast.next.next;
        if(slow == fast)
        {
            break;
        }
    }

    if (slow != fast) return null;

    fast = head;
    // A = N * (环路长度) - B，可以理解为一个指针从起点开始走，另一个指针走了N圈减去B的
    // 长度，因为这里慢指针已经停在了相遇点，既已经从一圈里减去了B
    while (slow != fast)
    {
        fast = fast.next;
        slow = slow.next;
    }

    return slow;
}