文章目录
- 1. 移除链表元素
- 2. 反转链表
- 3. 找链表中间节点
- 4. 合并两个有序的链表
- 5. 分割链表
- 6. 链表的回文结构
- 7. 相交链表
- 8. 判断环形链表
- 9. 返回环形链表的入环节点
- 10. 随机链表的复制
1. 移除链表元素
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef struct ListNode {int val;struct ListNode* next;
}NodeList;NodeList* removeElements(NodeList* head, int val)
{assert(head);NodeList* newhead = NULL; NodeList* newtail = NULL; NodeList* pcur = head;while (pcur){if (pcur->val != val){if (newhead == NULL)newhead = newtail = pcur;else{newtail->next = pcur;newtail = newtail->next;}}pcur = pcur->next;}if (newtail)newtail->next = NULL;return newhead;
}
void NodeListPrint(NodeList* phead)
{assert(phead);while (phead){printf("%d -> ", phead->val);phead = phead->next;}printf("NULL\n");
}void test()
{NodeList* node1 = (NodeList*)malloc(sizeof(NodeList));NodeList* node2 = (NodeList*)malloc(sizeof(NodeList));NodeList* node3 = (NodeList*)malloc(sizeof(NodeList));NodeList* node4 = (NodeList*)malloc(sizeof(NodeList));NodeList* node5 = (NodeList*)malloc(sizeof(NodeList));NodeList* node6 = (NodeList*)malloc(sizeof(NodeList));NodeList* node7 = (NodeList*)malloc(sizeof(NodeList));if (node1 == NULL || node2 == NULL || node3 == NULL || node4 == NULL || node5 == NULL || node6 == NULL || node7 == NULL){perror("malloc");exit(1);}node1->val = 1;node2->val = 2;node3->val = 6;node4->val = 3;node5->val = 3;node6->val = 5;node7->val = 6;node1->next = node2;node2->next = node3;node3->next = node4;node4->next = node5;node5->next = node6;node6->next = node7;node7->next = NULL;printf("移除之前链表为>:");NodeListPrint(node1);NodeList* newnode = removeElements(node1, 6);printf("移除之后链表为>:");NodeListPrint(newnode);}
int main()
{test();return 0;
}
2. 反转链表
typedef struct ListNode {int val;struct ListNode* next;
}ListNode;
ListNode* reverseList(ListNode* head)
{if (head == NULL)return head;ListNode* n1, * n2, * n3;n1 = NULL;n2 = head;n3 = n2->next;while (n2){n2->next = n1;n1 = n2;n2 = n3;if (n3)n3 = n3->next;}return n1;
}
void ListNodePrint(ListNode* phead)
{assert(phead);while (phead){printf("%d -> ", phead->val);phead = phead->next;}printf("NULL\n");
}void test()
{ListNode* node1 = (ListNode*)malloc(sizeof(ListNode));ListNode* node2 = (ListNode*)malloc(sizeof(ListNode));ListNode* node3 = (ListNode*)malloc(sizeof(ListNode));ListNode* node4 = (ListNode*)malloc(sizeof(ListNode));ListNode* node5 = (ListNode*)malloc(sizeof(ListNode));if (node1 == NULL || node2 == NULL || node3 == NULL || node4 == NULL || node5 == NULL){perror("malloc");exit(1);}node1->val = 1;node2->val = 2;node3->val = 3;node4->val = 4;node5->val = 5;node1->next = node2;node2->next = node3;node3->next = node4;node4->next = node5;node5->next = NULL;printf("反转链表之前为>:");ListNodePrint(node1);ListNode* newnode = reverseList(node1);printf("反转链表之后为>:");ListNodePrint(newnode);}
int main()
{test();return 0;
}
3. 找链表中间节点
typedef struct ListNode
{int val;struct ListNode* next;
}ListNode;
ListNode* middleNode(ListNode* head)
{ListNode* slow = head;ListNode* fast = head;while (fast && fast->next){slow = slow->next;fast = fast->next->next;}return slow;
}
void ListNodePrint(ListNode* phead)
{assert(phead);while (phead){printf("%d -> ", phead->val);phead = phead->next;}printf("NULL\n");
}void test()
{ListNode* node1 = (ListNode*)malloc(sizeof(ListNode));ListNode* node2 = (ListNode*)malloc(sizeof(ListNode));ListNode* node3 = (ListNode*)malloc(sizeof(ListNode));ListNode* node4 = (ListNode*)malloc(sizeof(ListNode));ListNode* node5 = (ListNode*)malloc(sizeof(ListNode));ListNode* node6 = (ListNode*)malloc(sizeof(ListNode));if (node1 == NULL || node2 == NULL || node3 == NULL || node4 == NULL || node5 == NULL || node6 == NULL){perror("malloc");exit(1);}node1->val = 1;node2->val = 2;node3->val = 3;node4->val = 4;node5->val = 5;node6->val = 6;node1->next = node2;node2->next = node3;node3->next = node4;node4->next = node5;node5->next = node6;node6->next = NULL;printf("链表为>:");ListNodePrint(node1);ListNode* newnode = middleNode(node1);printf("链表中间节点为>: %d\n", newnode->val);
}
int main()
{test();return 0;
}
4. 合并两个有序的链表
typedef struct ListNode
{int val;struct ListNode* next;
}ListNode;
ListNode* mergeTwoLists2(ListNode* list1, ListNode* list2)
{if (list1 == NULL)return list2;if (list2 == NULL)return list1;ListNode* l1 = list1;ListNode* l2 = list2;ListNode* newHead, * newTail;newHead = newTail = (ListNode*)malloc(sizeof(ListNode));while (l1 && l2){if (l1->val < l2->val){newTail->next = l1;newTail = newTail->next;l1 = l1->next;}else{newTail->next = l2;newTail = newTail->next;l2 = l2->next;}}if (l1)newTail->next = l1;if (l2)newTail->next = l2;ListNode* retnode = newHead->next;free(newHead);newHead = NULL;return retnode;
}
void ListNodePrint(ListNode* phead)
{assert(phead);while (phead){printf("%d -> ", phead->val);phead = phead->next;}printf("NULL\n");
}void test()
{ListNode* node1 = (ListNode*)malloc(sizeof(ListNode));ListNode* node2 = (ListNode*)malloc(sizeof(ListNode));ListNode* node3 = (ListNode*)malloc(sizeof(ListNode));ListNode* node4 = (ListNode*)malloc(sizeof(ListNode));ListNode* node5 = (ListNode*)malloc(sizeof(ListNode));ListNode* node6 = (ListNode*)malloc(sizeof(ListNode));if (node1 == NULL || node2 == NULL || node3 == NULL || node4 == NULL || node5 == NULL || node6 == NULL){perror("malloc");exit(1);}node1->val = 1;node2->val = 2;node3->val = 4;node4->val = 1;node5->val = 3;node6->val = 4;node1->next = node2;node2->next = node3;node3->next = NULL;node4->next = node5;node5->next = node6;node6->next = NULL;printf("合并之前链表1为>:");ListNodePrint(node1);printf("合并之前链表2为>:");ListNodePrint(node4);ListNode* newnode = mergeTwoLists2(node1, node4);printf("合并链表之后>:");ListNodePrint(newnode);
}
int main()
{test();return 0;
}
5. 分割链表
6. 链表的回文结构
- 题目:回文结构,左右对称,例如:1221,12121,12321
- 思路1:创建新数组,保存链表中所有节点的值,然后再判断数组是否是回文结构即可
#include <stdbool.h>
typedef struct ListNode
{int val;struct ListNode* next;
}ListNode;
bool chkPalindrome(ListNode* A)
{int arr[900] = { 0 };int i = 0;ListNode* pcur = A;while (pcur) {arr[i++] = pcur->val;pcur = pcur->next;}int left = 0;int right = i - 1;while (left < right) {if (arr[left] != arr[right])return false;left++;right--;}return true;
}
- 虽然这种方法一定程度帮助我们解题,但该方法受到链表长度的限制,而且严重存在浪费空间
- 思路2:反转链表中间节点之后的一段链表,然后对比前后两段
#include <stdbool.h>
typedef struct ListNode
{int val;struct ListNode* next;
}ListNode;
ListNode* middleNode(struct ListNode* head)
{ListNode* slow = head;ListNode* fast = head;while (fast && fast->next){slow = slow->next;fast = fast->next->next;}return slow;
}
ListNode* reverseList(ListNode* head)
{if (head == NULL)return head;ListNode* n1, * n2, * n3;n1 = NULL;n2 = head;n3 = n2->next;while (n2) {n2->next = n1;n1 = n2;n2 = n3;if (n3)n3 = n3->next;}return n1;
}
bool chkPalindrome(ListNode* A)
{ListNode* mid = middleNode(A);ListNode* right = reverseList(mid);ListNode* left = A;while (right) {if (left->val != right->val) {return false;}left = left->next;right = right->next;}return true;
}
#include <stdbool.h>
typedef struct ListNode
{int val;struct ListNode* next;
}ListNode;
ListNode* reverseList(ListNode* head)
{if (head == NULL)return head;ListNode* n1, * n2, * n3;n1 = NULL; n2 = head; n3 = n2->next;while (n2){n2->next = n1;n1 = n2;n2 = n3;if (n3)n3 = n3->next;}return n1;
}
bool chkPalindrome(ListNode* A)
{ListNode* newNode = reverseList(A);ListNode* pcur = A;while (pcur){if (pcur->val != newNode->val)return false;pcur = pcur->next;newNode = newNode->next;}return true;
}
7. 相交链表
typedef struct ListNode
{int val;struct ListNode* next;
}ListNode;typedef struct ListNode ListNode;
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
{ListNode* pa = headA;ListNode* pb = headB;int sizeA = 0, sizeB = 0; while (pa){pa = pa->next;sizeA++;}while (pb){pb = pb->next;sizeB++;}int gap = abs(sizeA - sizeB); ListNode* longList = headA;ListNode* shortList = headB;if (sizeA < sizeB){longList = headB;shortList = headA;}while (gap--){longList = longList->next;}while (shortList){if (shortList == longList)return shortList;shortList = shortList->next;longList = longList->next;}return NULL;
}
8. 判断环形链表
#include <stdbool.h>
typedef struct ListNode ListNode;
typedef struct ListNode
{int val;struct ListNode* next;
}ListNode;bool hasCycle(struct ListNode* head)
{ListNode* slow = head;ListNode* fast = head;while (fast && fast->next){slow = slow->next;fast = fast->next->next;if (slow == fast)return true;}return false;
}
- 思考:为什么在环形链表中,快指针走两步,慢指针走一步,两个一定会相遇?
9. 返回环形链表的入环节点
typedef struct ListNode ListNode;
typedef struct ListNode
{int val;struct ListNode* next;
}ListNode;struct ListNode* detectCycle(struct ListNode* head)
{ListNode* slow = head;ListNode* fast = head;while (fast && fast->next){slow = slow->next;fast = fast->next->next;if (slow == fast){ListNode* pcur = head; while (pcur != slow){pcur = pcur->next;slow = slow->next;}return pcur;}}return NULL;
}
- 证明在带环链表中,相遇点和头节点到入环第一个节点的距离相等
10. 随机链表的复制
typedef struct Node
{int val;struct Node* next;struct Node* random;
}ListNode;typedef struct Node Node;
Node* BuyNode(int x)
{Node* node = (Node*)malloc(sizeof(Node));if (node == NULL)return -1;node->val = x;node->next = node->random = NULL;return node;
}
void AddNode(Node* head)
{Node* pcur = head;while (pcur){Node* next = pcur->next; Node* newnode = BuyNode(pcur->val);newnode->next = next;pcur->next = newnode;pcur = next;}
}
void Setrandom(Node* head)
{Node* pcur = head;while (pcur){Node* copy = pcur->next;if (pcur->random)copy->random = pcur->random->next;pcur = copy->next;}
}
struct Node* copyRandomList(struct Node* head)
{if (head == NULL){return head;}AddNode(head);Setrandom(head);Node* newHead, * newTail;Node* pcur = head;newHead = newTail = pcur->next;while (newTail->next){pcur = newTail->next;newTail->next = pcur->next;newTail = newTail->next;}return newHead;
}