链表(linked list)是一种常见的线性数据结构。常见的链表分类有：单向链表，双向链表，循环链表，静态链表等。

链表节点结构

链表结构又分为带头结构的链表与不带头结构的链表。

单向链表

1
2
3
4
5
6
7
8
9
10
11
12
13
struct Node {
  int data;
  struct Node *next;
}
/* 链表头，可带可不带 */
struct Header {
  int length;
  struct Node *next;
};

typedef struct Node Node;
typedef struct Header pHead;

双向链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct Node;
typedef struct Header* pHead;
typedef struct Node* pNode;

struct Header{
  int length;
  pNode next;
};

struct Node{
  int data;
  pNode pre;
  pNode next;
};

循环链表与单向链表或双向链表结构相同，只是尾指针不指向NULL，而是指向头节点。

链表的基础操作

插入

双向链表的插入

1
2
3
4
pNode->next = pCur->next;
pCur->next->pre = pNode;
pNode->pre = pCur;
pCur->next = pNode;

删除

1
2
3
4
pPre = pDelete->pre;
pNext = pDelete->next;
pPre->next = pNext;
pNext->pre = pPre;

链表的常见考点

反转链表

迭代反转链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
node* ReverseList(node* pHead){
  node* pTemp = pHead;
  node* pReverse = NULL;

  if(pHead == NULL || pHead->_next == NULL)
    return pHead;

  while(pTemp != NULL){
    node* pNextNode = pTemp->_next;
    pTemp->_next = pReverse;
    pPreverse = pTemp;
    pTemp = pNextNode;
  }

  return pReverse;
}

在迭代链表中：

  1. pTemp指针用于遍历要反转的链表。
  2. pNextNode临时保存pTemp->_next指针。
  3. pReverse指向反转后链表的头指针。

递归反转链表

递归反转链表

1
2
3
4
5
6
7
8
9
10
11
12
13
node* ReverseList_DG(node* pHead){
  node* pNewHead = NULL;

  if(pHead == NULL || pHead->_next == NULL)
    return pHead;

  pNewHead = ReverseList_DG(pHead->_next);

  pHead->_next->_next = pHead;
  pHead->_next = NULL;

  return pNewHead;
}

合并有序链表

LeetCode 21.合并两个有序链表

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例:

1
2
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->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
30
31
32
33
34
35
36
37
38
39
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
    struct ListNode *begin = malloc(sizeof(struct ListNode));
    struct ListNode *tmp_p = begin;
    struct ListNode *l1_p = l1;
    struct ListNode *l2_p = l2;
    while(l1_p != NULL || l2_p != NULL){
        struct ListNode *a = malloc(sizeof(struct ListNode));
        tmp_p->next = a;
        if(l1_p == NULL){
            a->val = l2_p->val;
            tmp_p = a;
            l2_p = l2_p->next;
        }else if(l2_p == NULL){
            a->val = l1_p->val;
            tmp_p = a;
            l1_p = l1_p->next;
        }else{
            if(l1_p->val > l2_p->val){
                a->val = l2_p->val;
                tmp_p = a;
                l2_p = l2_p->next;
            }else{
                a->val = l1_p->val;
                tmp_p = a;
                l1_p = l1_p->next;
            }
        }
    }
    tmp_p->next = NULL;

    return begin->next;
}

递归解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
	if (l1 == NULL) {
		return l2;
	}
	else if (l2 == NULL) {
		return l1;
	}

    if(l1->val < l2->val){
        l1->next = mergeTwoLists(l1->next,l2);
        return l1;
    }else{
        l2->next = mergeTwoLists(l1,l2->next);
        return l2;
    }
}

查找中间节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
node* SearchMidNode(node* pHead){
  node* pFast = pHead;
  node* pSlow = pHead;

  if(pHead == NULL || pHead->_next == NULL)
    return NULL;

  while(pFast != NULL && pFast->_next != NULL){
    pSlow = pSlow->_next;
    pFast = pFast->_next->_next;
  }
  
  return pSlow;
}

查找倒数第K个节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
node* FindLastKNode(node* pHead, int key){
  node* pSlow = pHead;
  node* pFast = pHead;
  
  if(pHead == NULL)
    return NULL;

  while(key--){
    if(pFast == NULL)
       return NULL;
    pFast = pFast->_next;
  }

  while(pFast != NULL){
    pFast = pFast->_next;
    pSlow = pSlow->_next;
  }

  return pSlow;
}

链表是否有环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
node * isHaveCircle(node* pHead){
  node* pFast = pHead;
  node* pSlow = pHead;

  if(pHead == NULL)
    return NULL;

  while(pFast != pSlow && pFast->_next != NULL){
    pFast = pFast->_next->_next;
    pSlow = pSlow->_next;
  }
  
  if(pFast->_next == NULL){
   return NULL;
  }

  return pSlow;
}

求环的入口节点

如图所示，当快慢指针相遇时，slow还没走完链表，fast指针已经在环内循环链n圈。假设slow指针走了s步，即链表头距相遇点为s，那么fast指针走链2s步，fast指针走过的长度还等于s+n*r，r为环的长度。则:
$$ 2 \ast s = s+n \ast r => s=n \ast r $$

假设整个链表长度为L，入口到相遇点的距离为x，起到到入口的距离为a，则有：$$ a+x=s=n \ast r $$ $$ a+x=(n-1) \ast r+r=(n-1) \ast r+(L-a) $$ $$ a=(n-1) \ast r+(L-a-x) $$

所以：在使用两个指针，从链表头与相遇点再次出发，两指针相遇点也就是链表环入口。

有环链表示意图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
node* GetCircleIntoNode(node* pHead){
  node* pBeginNode = pHead;
  node* pMeetNode = NULL;

  pMeetNode = isHaveCircle(pHead);
  if(!pMeetNode){
    return NULL;
  }

  while(pBeginNode != pMeetNode){
    pBeginNode = pBeginNode->_next;
    pMeetNOde = pMeetNode->_next;
  }

  return pMeetNode;
}

求环的长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int GetCircleLength(node* pHead){
  size_t len = 0;
  node* pMeetNode = NULL;
  node* pCur = NULL;

  if((pMeetNode = isHaveCircle(pHead)) == NULL)
    return 0;

  pCur = pMeetNode->_next;

  while(pCur != pMeetNode){
    len++;
    pCur = pCur->_next;
  }

  return len;
}

求有环链表的长度

链表长度L = 起点到入口点的距离a + 环的长度r 。

静态链表

在此不展开讲，放两篇文章：

  1. 静态链表及C语言实现
  2. 被人遗忘了的静态链表