Leetcode Linked Lists practice summary
帶头结点的单链表的基本功能实现。
#define ElemType int
typedef struct LNode{
ElemType data;
struct LNode* next;
}LNode;
typedef struct {
LNode* head;
int length;
} MyLinkedList;
/** Initialize your data structure here. */
MyLinkedList* myLinkedListCreate() {
MyLinkedList* obj = (MyLinkedList*)malloc(sizeof(MyLinkedList));
if(!obj){
return;
}
obj->head = (LNode*)malloc(sizeof(LNode));
if(!obj->head){
return;
}
obj->head->data = -1;
obj->head->next = NULL;
obj->length = 0;
return obj;
}
/** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
int myLinkedListGet(MyLinkedList* obj, int index) {
LNode* curr = obj->head;
if(index < 0 || index >= obj->length)
return -1;
for(int i = 0; i <= index; i++){
curr = curr->next;
}
return curr->data;
}
/** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
void myLinkedListAddAtHead(MyLinkedList* obj, int val) {
LNode* head = obj->head;
LNode* temp = (LNode*)malloc(sizeof(LNode));
temp->data = val;
temp->next = head->next;
head->next = temp;
obj->length++;
}
/** Append a node of value val to the last element of the linked list. */
void myLinkedListAddAtTail(MyLinkedList* obj, int val) {
LNode* curr = obj->head;
LNode* temp = (LNode*)malloc(sizeof(LNode));
if(!temp){
return;
}
temp->data = val;
temp->next = NULL;
while(curr->next){
curr = curr->next;
}
curr->next = temp;
obj->length++;
}
/** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
void myLinkedListAddAtIndex(MyLinkedList* obj, int index, int val) {
LNode* prev,*curr;
prev = obj->head;
curr = prev->next;
LNode* temp = (LNode*)malloc(sizeof(LNode));
if(!temp){
return;
}
if(index > obj->length)
return;
temp->data = val;
for(int i = 0; i < index; i++){
prev = prev->next;
curr = curr->next;
}
temp->next = curr;
prev->next = temp;
obj->length++;
}
/** Delete the index-th node in the linked list, if the index is valid. */
void myLinkedListDeleteAtIndex(MyLinkedList* obj, int index) {
LNode* prev,*curr;
prev = obj->head;
curr = prev->next;
if(index < 0 || index >= obj->length)
return -1;
for(int i = 0; i < index; i++){
prev = prev->next;
curr = curr->next;
}
prev->next = curr->next;
free(curr);
obj->length--;
}
void myLinkedListFree(MyLinkedList* obj) {
LNode* prev,*curr;
prev = obj->head;
curr = prev->next;
while(curr){
prev->next = curr->next;
free(curr);
curr = prev->next;
}
free(obj);
}
一开始使用遍历的方法，现在感觉使用两个指针，一个速度是另一个2倍，可能更加方便。
struct ListNode* reverseList(struct ListNode* head){
if(head == NULL || head->next == NULL) //当头指针为空或者只有一个结点时停止递归
return head;
struct ListNode* newhead = reverseList(head->next); //递归
/////尾插法
head->next->next = head;
head->next = NULL;
/////end
return newhead;
}
每次假设除了第一个结点外其他结点已经翻转完毕（此时head->next是已经翻转后新链表的最后一个结点），然后将头结点插入新链表的尾部（即head->next）。
void deleteNode(struct ListNode* node) {
struct ListNode* temp = node->next;
node->val = temp->val;
node->next = temp->next;
free(temp);
}
题目难点在于只给出了需要删除的结点，
解题思路：将下一个结点的val复制给当前结点，然后删除下一个结点。即用当前结点代替下一个结点。
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
if (l1 == NULL)
return l2;
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;
}
}
每次在两个链表的第一个结点中选择较小的一个，然后假设除了该结点其他结点已经合并完毕。在这种情况下只需要令该结点指向已排序好的新链表即可。不断递归，问题规模不断减小，直到有一个链表为NULL时停止递归。
struct ListNode* deleteDuplicates(struct ListNode* head){
struct ListNode* temp;
if(head == NULL)
return NULL;
if(head->next == NULL)
return head;
if(head->val == head->next->val){
temp = head;
head = deleteDuplicates(head->next);
free(temp);
}
else
head->next = deleteDuplicates(head->next);
return head;
}
每次判断前两个结点的val是否相同，如果相同，假设除了第一个结点外链表已经去重完毕，此时只需要将头指针指向新链表即可。如果不相同，令第一个节点指向新链表。不断递归，问题规模不断减小，直到只有一个结点时停止。
使用 Floyd Cycle Detection Algorithm 又叫Tortoise and Hare Algorithm
struct ListNode* reverse(struct ListNode* head){
struct ListNode* p,*temp;
p = head->next;
head->next = NULL;
/////////后插法//////////////
while(p !=NULL){
temp = p->next;
p->next = head;
head = p;
p = temp;
}
//////////后插法//////////
return head;
}
bool isPalindrome(struct ListNode* head){
struct ListNode* slow =head,*fast =head;
if(!head || !head->next) return true;
////////找到中间结点和尾结点
while(fast->next && fast->next->next ){
fast = fast->next->next;
slow = slow->next;
}
if(fast->next){
fast = fast->next;
slow = slow->next;
}
//////end
//////翻转链表
reverse(slow);
//////end
/////逐个结点检查
while(fast){
if(fast->val == head->val){
fast = fast->next;
head = head->next;
}
else
return false;
}
return true;
}
解题思想在于，找到中间结点然后reverse后半段的链表，并与前半段对比。
struct ListNode* removeElements(struct ListNode* head, int val){
struct ListNode* dummy=(struct ListNode*)malloc(sizeof(struct ListNode));
dummy->val=INT_MAX;
dummy->next=head;
struct ListNode* prev = dummy;
struct ListNode* Next = NULL;
struct ListNode* curr = dummy->next;
while(curr){
Next=curr->next;
if(curr->val==val){
prev->next=curr->next;
free(curr);
}
else
prev=curr;
curr=Next;
}
return dummy->next;
}
d算法本身没什么好说的，不过值得注意的是，使用头结点将第一个结点普通化，不用单独处理第一个结点，更加方便。个人感觉链表的核心就在于 prev & curr & next。
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
int LengthA = 0, LengthB = 0;
struct ListNode* curr;
curr = headA;
while(curr){
curr = curr->next;
LengthA++;
}
curr = headB;
while(curr){
curr = curr->next;
LengthB++;
}
while(LengthA < LengthB){
headB = headB->next;
LengthB--;
}
while(LengthB < LengthA){
headA = headA->next;
LengthA--;
}
while(headA != headB){
headA = headA->next;
headB = headB->next;
}
return headA;
}
b遍历，确定两个链表的长度，然后将较长的链表缩短到于短链表一样的长度。最后逐结点对比，当发现指针相同时，就是解。