1.1 LeetCode总结（线性表）_链表类_leetcode c语言 链表 库

编程总结

每每刷完一道题后，其思想和精妙之处没有地方记录，本篇博客用以记录刷题过程中的遇到的算法和技巧

203. 删除链表的节点

法一：需要单独处理头结点和非头结点

struct ListNode *deleteNode(struct ListNode *head, int val)
{
	struct ListNode *tmp = head;
	struct ListNode *pre = NULL;
	struct ListNode *cur = NULL;
	int    index = 0;

	while (tmp->next != NULL) {
		if (tmp->val == val) {
			break;
		}
		tmp = tmp->next;
		index++;
	}
	cur = tmp;
	// 1. 删除的是 head 节点.
	if (index == 0) { 
		struct ListNode *node = tmp->next;
		tmp->next = NULL;
		return node;
	}
	// 2. 否则，非 head 节点，那就先找到 pre 节点.
	tmp = head;
	while (index > 1) {
		tmp = tmp->next;
		index--;
	}
	pre = tmp;
	pre->next = cur->next;
	cur->next = NULL;
	cur->val  = 0;
	return head;
}
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

法二：创建虚拟头结点，来处理

struct ListNode *removeElements(struct ListNode *head, int val)
{
    struct ListNode *dummyHead = malloc(sizeof(struct ListNode));
    dummyHead->next = head;
    struct ListNode *temp = dummyHead;
    while (temp->next != NULL) {
        if (temp->next->val == val) {
            temp->next = temp->next->next;
        } else {
            temp = temp->next;
        }
    }
    return dummyHead->next;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

***. 链表基本操作

typedef struct ListNode_t {
	int val;
	struct ListNode_t *next;
} ListNode;

// 1.创建链表
ListNode *ListCreate() {
	// 在链表的第一个结点之前会额外增设一个结点，头结点
	ListNode *head = (ListNode *)malloc(sizeof(ListNode));
	if (head == NULL) {
		return NULL;
	}
	head->next = NULL;
	head->val = 0; // 头结点的val用来指示链表长度

	return head;
}
// 2.获取链表中第index个节点的索引值，如果索引无效，则返回-1
int ListIndexGet(ListNode *obj, int index)
{
	int cnt = 0;
	ListNode *tmp = obj->next; // 手法:  因为我们是以首元结点开始index为0，所以要obj->next以首元开始
							   // 而不是 ListNode *tmp = obj; 
	while (tmp) {
		if (index == cnt) {
			return tmp->val;
		}
		cnt++;
		tmp = tmp->next;
	}
	return -1;
}

// 首元结点：链表中第一个元素所在的结点，它是头结点后边的第一个结点
/* 在链表的第一个元素之前添加值为val的节点。插入后，新节点将成为链表的第一个节点 */
/* obj -> node1 -> node2 */
/* obj -> newNode  -> node1 -> node2 */
void ListAddAtHead(ListNode *obj, int val)
{
	ListNode *newNode = (ListNode *)malloc(sizeof(ListNode));
	if (newNode == NULL) {
		return;
	}
	obj->val++; // 记录链表长度
	newNode->val = val;
	newNode->next = obj->next;
	obj->next = newNode;
}

/*  将值为val的节点附加到链表的最后一个元素 */
/*  head  -> node1 -> node2 */
/*  head  -> node1 -> node2 -> tail */
void ListAddAtTail(ListNode *obj, int val)
{
	ListNode *tail = (ListNode *)malloc(sizeof(ListNode));
	ListNode *tmp  = obj;
	if (tail == NULL) {
		return;
	}
	obj->val++; // 记录链表长度
	tail->val = val;
	tail->next = NULL;
	while (tmp->next) {
		tmp = tmp->next;
	}
	tmp->next = tail;
}

/* 在链表的索引节点之前添加一个值为val的节点。如果索引等于链表的长度，
   则节点将附加到链表的末尾。如果索引大于长度，则不会插入节点 */
/* obj -> node1 -> node2 */
/* obj -> node1 -> newNode -> node2 */
void ListAddAtIndex(ListNode *obj, int index, int val)
{
	int cnt = 0;
	if (index == obj->val) {
		ListAddAtTail(obj, val);
		return;
	} else if (index > obj->val) {
		return;
	}
	ListNode *tmp = obj;
	ListNode *newNode = (ListNode *)malloc(sizeof(ListNode));
	newNode->val = val;
	while (tmp) {
		if (cnt == index) {
			break;
		}
		tmp = tmp->next;
		cnt++;
	}
	obj->val++; // 记录链表长度
	newNode->next = tmp->next;
	tmp->next = newNode;
	return;
}

/* 如果索引有效，请删除链表中的第index个节点 */
/*  head  -> node1 -> node2 -> node3 */
/*  head  -> node1 -> node3          */
void ListDeleteAtIndex(ListNode *obj, int index)
{
	ListNode *node = NULL;
	ListNode *tmp = obj;
	int cnt = 0;
	while (tmp) {
		if (cnt == index) {
			break;
		}
		cnt++;
		tmp = tmp->next;
	}
	if (tmp->next == NULL) { // 删除的是最后的NULL，直接返回，手法
		return;
	}
	obj->val--;
	node = tmp->next;
	tmp->next = node->next;
	free(node);
}
/*  head  -> node1 -> node2 -> node3 */
void ListFree(ListNode *obj)
{
	ListNode *tmp = obj;
	ListNode *freeNode;

	while (tmp) {  // 释放头结点->首元结点内的
		freeNode = tmp;
		tmp = tmp->next;
		freeNode->next = NULL;
		freeNode->val = 0;
		free(freeNode);
	}
}
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134

206. 反转链表

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

下图一到图二进行了四个步骤的变化：

法一：双指针法

struct ListNode *reverseList(struct ListNode *head) {
	ListNode *pre = NULL; // 需要指向前一个元素的指针，因为要转向，所以先来一个pre
	ListNode *cur = head;
    while (cur != NULL)   // cur移动到NULL，此时pre就是新链表的第一个节点
    {
        // 1. 转向
		ListNode *next = cur->next; // 保存 cur 的 next 节点
        cur->next = pre;  // cur新的next指向pre，也就是节点反向，同时，此时cur之前的next就断了，也是为什么要先保留cur->next 的原因  
        // 2. 平移 继续之前的操作，先保留next，然后反向cur->next，然后平移
        pre = cur;        // 平移pre节点
        cur = next;       // 平移cur节点
    }
    return pre; // 新链表的头结点，pre
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

法二：数组记录法
因为题目其实只看数值是否反转了，所以也可以使用将链表存放到数组里，再反转的思路解题：

struct ListNode *reverseList(struct ListNode *head) 
{
	int capacity;
	struct ListNode *tmp = head;
	int index = 0;

	// 1.计算capacity
	while (tmp != NULL) {
		index++;
		tmp = tmp->next;
	}
	capacity = index;
	int *res = (int *)malloc(sizeof(int)*capacity);
	index = 0;
	tmp = head;
	// 2.将链表的值转移到数组里
	while (tmp != NULL) {
		res[index++] = tmp->val;
		tmp = tmp->next;
	}
	tmp = head;
	index = index - 1;
	// 3.反转赋值回链表里
	while (tmp != NULL) {
		tmp->val = res[index--];
		tmp = tmp->next;
	}
	free(res);

	return head;
}
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

19. 删除链表的倒数第 N 个结点

思路：
这题常规解决要处理的思路是不好删除首节点，比如：链表 [1,2] 想删除倒数第2个节点 1.

在对链表进行操作时，一种常用的技巧是添加一个哑节点（dummy node），它的 next 指针指向链表的头节点。这样一来，想操作头节点一样的处理手法即可，不需要额外处理。
dummy->next = head; 和 203. 删除链表节点 一个手法~

// 特殊处理如果删除的首节点的情况，比如 [1,2] 删除倒数第2个节点.  
int getLength(struct ListNode *head) {
    int length = 0;
    while (head) {
        ++length;
        head = head->next;
    }
    return length;
}
// 如果要删除头结点，那么会找到dummy节点，通过将 cur->next = cur->next->next 来删除头节点
struct ListNode *removeNthFromEnd(struct ListNode *head, int n) {
    struct ListNode *dummy = malloc(sizeof(struct ListNode));
    dummy->val = 0, dummy->next = head;
    int length = getLength(head);
    struct ListNode *cur = dummy;
    // 倒数第N个，即正数第 len-n 个, 遍历到第 len−n+1 个节点进行处理
    for (int i = 1; i < length - n + 1; ++i) {
        cur = cur->next;
    }
    cur->next = cur->next->next; // 删除原来的cur->next 即 len-n 个节点
    struct ListNode *ans = dummy->next; 
    free(dummy);
    return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

21. 合并两个有序链表

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

struct ListNode *mergeTwoLists(struct ListNode *l1, struct ListNode *l2) {

    int length_l1 = 0;
    int length_l2 = 0;
    struct ListNode *head = NULL;
    struct ListNode *res  = NULL;
    struct ListNode *l1_t  = l1;
    struct ListNode *l2_t  = l2;

    if (l1 == NULL && l2 == NULL) {
        return NULL;
    }
    // 1.计算 l1 l2 的length
    while(l1_t != NULL) {
        l1_t = l1_t->next;
        length_l1++;
    }
    while(l2_t != NULL) {
        l2_t = l2_t->next;
        length_l2++;
    }
    // 新建一个新的链表
    head = (struct ListNode *)malloc((length_l1 + length_l2)*sizeof(struct ListNode ));
    res  = head;

    while (l1 != NULL || l2 != NULL) {
        // 特殊情况处理
        if (l1 == NULL) {
            head->next = l2;
            l2 = l2->next;
            head = head->next;
        }
        else if (l2 == NULL) {
            head->next = l1;
            l1 = l1->next;
            head = head->next;
        }
        // 2.哪个小赋值到新的链表里去
        else if (l1 != NULL && l2 != NULL) {
            if (l1->val <= l2->val) {
                head->next = l1;
                head = head->next;
                l1   = l1->next;
            } else {
                head->next = l2;
                head = head->next;
                l2   = l2->next;
            }
        }
    }
    return res->next;
}
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
40
41
42
43
44
45
46
47
48
49
50
51
52

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

	// 注意是 malloc(sizeof(struct ListNode));
	// 不是   malloc(sizeof(struct ListNode *));
	// 区别是 malloc 一个指针指向 大小为 ListNode
	struct ListNode *head = NULL;
	head = (struct ListNode *)malloc(sizeof(struct ListNode));
1
2
3
4
5

83. 给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次

struct ListNode *deleteDuplicates(struct ListNode *head)
{
	struct ListNode *cur = head;
	int value = 0;
	int value_next = 0;
	
	while (cur != NULL && cur->next != NULL) {
		value = cur->val;	
		value_next = cur->next->val;
		if (value == value_next) {
			cur->next = cur->next->next; // 注意不是：cur = cur->next->next;
		} else {
			cur = cur->next;
		}
	}

	return head;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

160. 相交链表 – 两个链表的第一个公共节点

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode *p = headA;
    struct ListNode *q = headB;
    while(p!=q)
    {
        if(p)
            p = p->next;
        else
            p = headB;
        if(q)## 标题
            q = q->next;
        else
            q = headA;
    }
    return q;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

–相交链表：“只要我们走一走彼此走过的路，就一定会相遇”
况一：两个链表相交

86. 分隔链表

给你一个链表和一个特定值 x ，请你对链表进行分隔，使得所有小于 x 的节点都出现在大于或等于 x 的节点之前。

你应当保留两个分区中每个节点的初始相对位置。

 struct ListNode {
      int val;
     struct ListNode *next;
 };

struct ListNode *partition(struct ListNode *head, int x)
{
	struct ListNode *p1 = (struct ListNode *)(malloc(sizeof(struct ListNode)));
	struct ListNode *p2 = (struct ListNode *)(malloc(sizeof(struct ListNode)));
	struct ListNode *head_tmp = head;
	struct ListNode *p1_tmp = (struct ListNode *)(malloc(sizeof(struct ListNode)));
	struct ListNode *p2_tmp = (struct ListNode *)(malloc(sizeof(struct ListNode)));
	p1->next = NULL;
	p2->next = NULL;
	p1_tmp = p1;
	p2_tmp = p2;

	while (head_tmp != NULL) {
		if (head_tmp->val < x) {
			p1_tmp->next = head_tmp;
			p1_tmp = head_tmp;
		}
		else {
			p2_tmp->next = head_tmp;
			p2_tmp = head_tmp;
		}
		head_tmp = head_tmp->next;
	}
	// contact
	p2_tmp->next = NULL;
	p1_tmp->next = p2->next;

	return p1->next;
}

int main(void)
{
	struct ListNode *value0 = (struct ListNode *)(malloc(sizeof(struct ListNode)));
	struct ListNode *value1 = (struct ListNode *)(malloc(sizeof(struct ListNode)));
	struct ListNode *value2 = (struct ListNode *)(malloc(sizeof(struct ListNode)));
	struct ListNode *value3 = (struct ListNode *)(malloc(sizeof(struct ListNode)));
	struct ListNode *value4 = (struct ListNode *)(malloc(sizeof(struct ListNode)));
	struct ListNode *value5 = (struct ListNode *)(malloc(sizeof(struct ListNode)));
	struct ListNode *res = (struct ListNode *)(malloc(sizeof(struct ListNode)));

	value0->val = 1;
	value1->val = 4;
	value2->val = 3;
	value3->val = 2;
	value4->val = 5;
	value5->val = 2;
	value0->next = value1;
	value1->next = value2;
	value2->next = value3;
	value3->next = value4; 
	value4->next = value5;
	value5->next = NULL;
	res = partition(value0, 3);
}
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

剑指 Offer 06. 从尾到头打印链表

int *reversePrint(struct ListNode *head, int *returnSize) 
{
	int len = 0;
	struct ListNode *tmp = head;
	int i = 0;

	while (tmp != NULL) {
		len++;
		tmp = tmp->next;
	}
	*returnSize = len;
	int *resTmp = (int *)malloc(sizeof(int)*len);
	int *res = (int *)malloc(sizeof(int)*len);
	tmp = head;

	while (tmp != NULL) {
		resTmp[i++] = tmp->val;
		tmp = tmp->next;
	}
	i = i - 1;
	for (int j = 0; j < len; j++) {
		res[j] = resTmp[i--];
	}
	free(resTmp);

	return res;
}
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

234. 回文链表

回文链表和回文数一样，是指完全可以中心对称的链表。
思路一：
一共为两个步骤：
复制链表值到数组列表中。
使用双指针法判断是否为回文。
思路二：
我们可以将链表的后半部分反转（修改链表结构），然后将前半部分和后半部分进行比较。比较完成后我们应该将链表恢复原样。
从实现上，第一种思路易于实现

bool isPalindrome(struct ListNode *head) 
{
	struct ListNode *tmp = head;
	int index = 0;
	int capacity = 0;
	int j;

	// 1. 计算链表容量 capacity.
	while (tmp != NULL) {
		tmp = tmp->next;
		index++;
	}
	capacity = index + 1;
	index = 0;
	tmp   = head;

	// 2. 将链表转移至数组.
	int *res = (int *)malloc(sizeof(int)*capacity);
	while (tmp != NULL) {
		res[index++] = tmp->val;
		tmp = tmp->next;
	}
	// 3.判断数组的值是否回文.
	j = index - 1;
	for (int i = 0; i <= j; ++i) {
		if (res[i] != res[j--]) {
			return false;
		}
	}
	free(res);

	return true;
}
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