leetcode--linked list

leetcode linked list

referenceintro1. 找交点2. Reverse Linked List(*)3. Merge Two Sorted Lists(*)4. delete duplicates(*)5. Remove Nth Node From End of List6. Swap Nodes in Pairs(*)7. add two linked list8. 检测回文

reference

linked list 题解

intro

很多链表问题可以用递归来处理。marked by （*） 这是刷题的初期可能还要复习下

1. 找交点

class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { ListNode *l1 = headA, *l2 = headB; //while two ptrs doesn't meet while (l1 != l2) { l1 = (l1) ? l1->next: headB; l2 = (l2) ? l2->next: headA; } return l1; } };

要求时间复杂度为 O(N)，空间复杂度为 O(1)。如果不存在交点则返回 null。

设 A 的长度为 a + c，B 的长度为 b + c，其中 c 为尾部公共部分长度，可知 a + c + b = b + c + a。

当访问 A 链表的指针访问到链表尾部时，令它从链表 B 的头部开始访问链表 B；同样地，当访问 B 链表的指针访问到链表尾部时，令它从链表 A 的头部开始访问链表 A。这样就能控制访问 A 和 B 两个链表的指针能同时访问到交点。

如果不存在交点，那么 a + b = b + a，以下实现代码中 l1 和 l2 会同时为 null，从而退出循环。

2. Reverse Linked List(*)

用递归的思路

class Solution { public: ListNode* reverseList(ListNode* head) { if(head == NULL || head->next == NULL){ return head; } ListNode* oldheadnext = head -> next; ListNode* newhead = reverseList(oldheadnext); //this is important, link the oldheadnext to original head oldheadnext -> next = head; //now head is the last entry head -> next = NULL; return newhead; } };

3. Merge Two Sorted Lists(*)

class Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { if(!l1){return l2;} if(!l2){return l1;} if(l1->val < l2-> val){ l1->next = mergeTwoLists(l1->next, l2); //this is key, as this recursion works in list one //it must have been finished before leveing this if return l1; } else{ l2->next = mergeTwoLists(l2->next, l1); return l2; } } };

4. delete duplicates(*)

用了C的语法和递归的思路

class Solution { public: ListNode* deleteDuplicates(ListNode* head) { if(head == NULL || head->next==NULL){ return head; } head->next = deleteDuplicates(head->next); return head->val == head->next->val ? head->next : head; } };

5. Remove Nth Node From End of List

使用快慢指针，一次遍历即可实现（！效率依然不高，有更优解）

class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* dummyhead = new ListNode(0); dummyhead->next = head; ListNode* fast = dummyhead; ListNode* slow = dummyhead; while(n-- >= 0){ fast = fast->next; //slow stay at head, now fast and slow are n apart } while(fast){ fast = fast -> next; slow = slow -> next; //push fast to the end, now slow's next is to be deleted } ListNode* tmp = slow->next; slow->next = tmp->next; delete tmp; head = dummyhead -> next; delete dummyhead; return head; } };

更优解

class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* fast = head; while (n-- > 0) { fast = fast->next; } //this is key, this means the list is shorter than n //so the head should be removed if (fast == NULL) return head->next; ListNode* slow = head; while (fast->next) { fast = fast->next; slow = slow->next; } ListNode* tmp = slow->next; slow->next = slow->next->next; delete tmp; return head; } };

6. Swap Nodes in Pairs(*)

用递归的思路，两两一组 时间复杂度：O(N)，其中 N 指的是链表的节点数量 *空间复杂度：O(N), 递归过程使用的堆栈空间

递归法：

class Solution { public: ListNode* swapPairs(ListNode* head) { ListNode * first, * second; if(head == NULL || head->next == NULL){ return head; } first = head; second = head->next; first->next = swapPairs(second->next); second->next=first; return second; } };

迭代法： 时间复杂度：O(N)，其中 N 指的是链表的节点数量 空间复杂度：O(1)

class Solution { public: ListNode* swapPairs(ListNode* head) { ListNode* dummy = new ListNode(0); dummy->next = head; ListNode* prevNode = dummy; while (head && head->next) { // Nodes to be swapped ListNode* firstNode = head; ListNode* secondNode = head->next; // Swapping prevNode->next = secondNode; // 放到交换前后都可以 firstNode->next = secondNode->next; secondNode->next = firstNode; // Reinitializing the head and prevNode for next swap prevNode = firstNode; head = firstNode->next; } return dummy->next; } };

7. add two linked list

! better solution exists

class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode *node1 = reverseListNode(l1); ListNode *node2 = reverseListNode(l2); return reverseListNode(add(node1,node2)); } private: ListNode* reverseListNode(ListNode* head){ if(head == NULL) return NULL; ListNode* prev = NULL; while (head != NULL) { ListNode* next = head->next; head->next = prev; prev = head; head = next; } return prev; } //两条链表中的各个节点数字相加 ListNode* add(ListNode* l1, ListNode* l2){ if (l1 == NULL && l2 == NULL) return NULL; ListNode* dummy = new ListNode(0); ListNode* temp = dummy; int addOne = 0; while (l1 || l2 || addOne != 0) { int val1 = !l1 ? 0 : l1->val; int val2 = !l2 ? 0 : l2->val; int sum = val1 + val2 + addOne; temp->next = new ListNode(sum); temp = temp->next; addOne = sum / 10; if (l1) l1 = l1->next; if (l2) l2 = l2->next; } temp = dummy->next; delete dummy; return temp; } };

8. 检测回文

注意这里reverse的使用和实现

class Solution { public: bool isPalindrome(ListNode* head) { if (head == NULL || head->next == NULL) return true; ListNode* slow = head, *fast = head->next; while (fast && fast->next ) { slow = slow->next; fast = fast->next->next; } if (fast){ ListNode* tmp = slow; slow = slow->next; tmp->next = NULL; } // 偶数节点，让 slow 指向下一个节点 return isEqual(head, reverse(slow)); } private: ListNode* reverse(ListNode* head) { ListNode* newHead = NULL; while (head) { ListNode* nextNode = head->next; head->next = newHead; newHead = head; head = nextNode; } return newHead; } bool isEqual(ListNode* l1, ListNode* l2) { while (l1 && l2) { if (l1->val != l2->val) return false; l1 = l1->next; l2 = l2->next; } return true; } };