本文主要介绍单链表常见的功能函数。

1 单链表常见功能函数

链表相关的功能有：反转链表，获取链表的长度，获取链表的中间结点，判断两条链表是否相加，判断链表是否有环，合并两个有序链表等。

1.1 翻转单链表

1.1.1 迭代方式翻转单链表

迭代方式翻转链表也称为链表头插法。

  • 方法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

// 新增额外头结点的
struct ListNode* reverseList(struct ListNode* head)
{
    if (head == NULL || head->next == NULL) {
        return head;
    }
    struct ListNode* headp = (struct ListNode*)malloc(sizeof(struct ListNode));
    headp->val = 0;
    headp->next = NULL;

    struct ListNode* tail = NULL;
    struct ListNode* cur = head;
    while (cur) {
        struct ListNode* pre = cur->next;
        tail = headp->next;
        headp->next = cur;
        cur->next = tail;

        cur = pre;
    }

    cur = headp->next;
    free(headp);
    headp = NULL;
    return cur;
}
  • 方法2：不新增头结点，进行翻转
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

struct ListNode* reverseList(struct ListNode* head)
{
    if (head == NULL || head->next == NULL) {
        return head;
    }

    struct ListNode* cur = head->next;
    head->next = NULL;
    while (cur) {
        struct ListNode* pre = cur->next;
        cur->next = head;
        head = cur;

        cur = pre;
    }

    return head;
}

1.1.2 递归方式翻转单链表

递归方式代码比较简单，但是要不太容易理解。递归的关键是抽象出一个通用的模型以及边界条件的处理。

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

struct ListNode* reverseList(struct ListNode* head)
{
    if (head == NULL || head->next == NULL) {
        return head;
    }

    struct ListNode* prev = reverseList(head->next);
    head->next->next = head;
    head->next = NULL;

    return prev;
}

1.2 获取单链表长度

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

int GetListNum(struct ListNode* head)
{
    if (head == NULL) {
        return 0;
    }

    int cnt = 0;
    struct ListNode* tmp = head;
    while (tmp) {
        ++cnt;
        tmp = tmp->next;
    }
    return cnt;
}

1.3 获取单链表中间结点

功能说明：

该函数返回链表中心点的前一个结点，即轴对称的尾结点。 例如，若链表有3个结点，则返回的是第1个结点的地址。若链表有4个结点，则返回的是第二个结点的地址。

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

struct ListNode* GetMidNode(struct ListNode* head)
{
    int cnt = GetListNum(head);
    int i = 0;
    tmp = head;
    struct ListNode* cur = NULL;
    while (i < cnt/2 && tmp) {
        cur = tmp;
        tmp = tmp->next;
        ++i;
    }

    return cur;
}

1.4 判断单链表是否存在环

方法说明：

  1. 方法1：使用hashtable。
  2. 方法2：使用快慢指针。具体方法是慢指针每次前进一步，快指针每次前进两步。若链表存在环，则经过若干步后，快指针肯定会追上慢指针，即两个指针指向同一个结点。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

bool hasCycle(struct ListNode *head)
{
    if (head == NULL || head->next == NULL) {
        return false;
    }
    struct ListNode* slow = head;
    struct ListNode* fast = head->next;

    while (slow != fast) {
        if (fast == NULL || fast->next == NULL) {
            return false;
        }
        slow = slow->next;
        fast = fast->next->next;
    }

    return true;
}

1.4.1 进阶：获取单链表环的入口结点

  1. 方法1：使用hashtable。
  2. 方法2：使用快慢指针。

2 链表高级特性

3 C++中的链表