141. Linked List Cycle
Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space?
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: bool hasCycle(ListNode *head) { if (head == NULL){ return false; } ListNode* slow = head; ListNode* fast = head; while (fast -> next != NULL && fast -> next -> next != NULL){ // 注意判断条件，第一次写的时候没有注意到要判断fast -> next是否为空 slow = slow -> next; fast = fast -> next -> next; if (fast == slow){ return true; } } return false; } };
160. Intersection of Two Linked Lists
Write a program to find the node at which the intersection of two singly linked lists begins.
For example, the following two linked lists:
A: a1 → a2
↘
c1 → c2 → c3
↗
B: b1 → b2 → b3
begin to intersect at node c1.
Notes:
- If the two linked lists have no intersection at all, return
null. - The linked lists must retain their original structure after the function returns.
- You may assume there are no cycles anywhere in the entire linked structure.
- Your code should preferably run in O(n) time and use only O(1) memory.
两种方法：
1. 利用两个栈去做，但是这不符合题目O(1)空间复杂度的要求
2. 很tricky的一种方法。双指针解决：
Two pointer solution (O(n+m) running time, O(1) memory):
- Maintain two pointers pA and pB initialized at the head of A and B, respectively. Then let them both traverse through the lists, one node at a time.
- When pA reaches the end of a list, then redirect it to the head of B (yes, B, that's right.); similarly when pB reaches the end of a list, redirect it the head of A.
- If at any point pA meets pB, then pA/pB is the intersection node.
- To see why the above trick would work, consider the following two lists: A = {1,3,5,7,9,11} and B = {2,4,9,11}, which are intersected at node '9'. Since B.length (=4) < A.length (=6), pB would reach the end of the merged list first, because pB traverses exactly 2 nodes less than pA does. By redirecting pB to head A, and pA to head B, we now ask pB to travel exactly 2 more nodes than pA would. So in the second iteration, they are guaranteed to reach the intersection node at the same time.
- If two lists have intersection, then their last nodes must be the same one. So when pA/pB reaches the end of a list, record the last element of A/B respectively. If the two last elements are not the same one, then the two lists have no intersections.
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { if (headA == NULL || headB == NULL){ return NULL; } ListNode* p1 = headA; ListNode* p2 = headB; while(p1 != p2){ p1 = p1 == NULL ? headB: p1 -> next; // 注意的一点是，这种条件判断也包含了当两个链表没有交点的情况，此时p1和p2都是NULL，会跳出循环， p2 = p2 == NULL ? headA: p2 -> next; } return p1; } };
二次刷：思路是a和b都开始一步一步的走，然后如果a走到了链表的尾部就从b的头部从新开始走，同理，如果b走到了链表的尾部就从a的头部开始走，不过要注意的是要对到达过链表的尾部做标记，这样才能判断链表有没有交点。代码写的有点啰嗦，其实就是上边的代码的 简洁版。。。没有对比就没有提高
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { if (headA == NULL || headB == NULL){ return NULL; } ListNode* pA = headA; ListNode* pB = headB; bool a = true; bool b = true; while (pA -> val != pB -> val){ pA = pA -> next; pB = pB -> next; if (pA == NULL) { if (a == false){ return NULL; } pA = headB; a = false; } if (pB == NULL){ if (b == false){ return NULL; } pB = headA; b = false; } } return pA; } };
或者很正常的一种思路：先求出两个链表的长度，求出长度的差值，然后用两个指针，一个指针先走长度的差值的那些步数，然后两个指针开始一块走，碰到的话就是交点，到了末尾就是没有交点。
19. Remove Nth Node From End of List
Given a linked list, remove the nth node from the end of list and return its head.
For example, Given linked list: 1->2->3->4->5, and n = 2. After removing the second node from the end, the linked list becomes 1->2->3->5.
Note:
Given n will always be valid.
Try to do this in one pass.
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { if (head == NULL){ return NULL; } ListNode* newp = new ListNode(0); // 要新建一个结点，来防止只有一个结点的情况出现 newp -> next = head; ListNode* slow = newp; ListNode* fast = newp; for (int i = 0; i <= n; i++){ fast = fast -> next; } while (fast != NULL){ slow = slow -> next; fast = fast -> next; } slow -> next = slow -> next -> next; return newp -> next; } };
==========
142. Linked List Cycle II
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.
Note: Do not modify the linked list.
Example 1:
Input: head = [3,2,0,-4], pos = 1 Output: tail connects to node index 1 Explanation: There is a cycle in the linked list, where tail connects to the second node.
Example 2:
Input: head = [1,2], pos = 0 Output: tail connects to node index 0 Explanation: There is a cycle in the linked list, where tail connects to the first node.
Example 3:
Input: head = [1], pos = -1 Output: no cycle Explanation: There is no cycle in the linked list.
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
if (!head) return NULL;
ListNode *slow = head;
ListNode *fast = head;
bool HasCycle = false;
while (fast->next != NULL && fast->next->next != NULL){
slow = slow -> next;
fast = fast -> next -> next;
if (fast == slow){
HasCycle = true;
break;
}
}
// 需要判断是否是有环的，若是有环，那么就
if (HasCycle){
// 若是有环，那么让fast 从头开始走，每次走一个结点。
fast = head;
while (slow != fast){
fast = fast ->next;
slow = slow ->next;
}
return fast;
}
return NULL;
}
};