gyzboy的十万个为什么
链表
链表的种类主要为：单链表，双链表，循环链表,链表的节点在内存中是分散存储的，通过指针连在一起
可以用来解决问题的方法:
- 虚拟头结点
- 双指针
- 分治法
输入:1->2->6->3->4->5->6,val=6
输出:1->2->3->4->5
关键点
- 创建虚拟头结点,用来删除第一个元素
ListNode* removeElements(ListNode* head, int val) {
ListNode* dummyHead = new ListNode(0); // 设置一个虚拟头结点
dummyHead->next = head; // 将虚拟头结点指向head，这样方面后面做删除操作
ListNode* cur = dummyHead;
while (cur->next != NULL) {
if(cur->next->val == val) {
ListNode* tmp = cur->next;
cur->next = cur->next->next;
delete tmp;
} else {
cur = cur->next;
}
}
return dummyHead->next;
}
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
关键点
- 双指针
ListNode* reverseList(ListNode* head) {
ListNode* temp; // 保存cur的下一个节点
ListNode* cur = head;
ListNode* pre = NULL;
while(cur) {
temp = cur->next; // 保存一下 cur的下一个节点，因为接下来要改变cur->next
cur->next = pre; // 翻转操作
// 更新pre 和 cur指针
pre = cur;
cur = temp;
}
return pre;
}
输入:1->3->5->7->6 K=3
输出:1->3->7->6
关键点
- 双指针
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummyHead = new ListNode(0);
dummyHead->next = head;
ListNode* slow = dummyHead;
ListNode* fast = dummyHead;
while(n-- && fast != NULL) {
fast = fast->next;
}
fast = fast->next; // fast再提前走一步，因为需要让slow指向删除节点的上一个节点
while (fast != NULL) {
fast = fast->next;
slow = slow->next;
}
slow->next = slow->next->next;
return dummyHead->next;
}
输入:1->3->4->2->3
输出:3
关键点
- 双指针
- 从头结点出发一个指针，从相遇节点 也出发一个指针，这两个指针每次只走一个节点， 那么当这两个指针相遇的时候就是 环形入口的节点
ListNode *detectCycle(ListNode *head) {
ListNode* fast = head;
ListNode* slow = head;
while(fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
// 快慢指针相遇，此时从head 和 相遇点，同时查找直至相遇
if (slow == fast) {
ListNode* index1 = fast;
ListNode* index2 = head;
while (index1 != index2) {
index1 = index1->next;
index2 = index2->next;
}
return index2; // 返回环的入口
}
}
return NULL;
}
输入: 1->2->2->1
输出: true
关键点
- 双指针
- 反转链表
public boolean isPalindrome(ListNode head) {
if (head == null) {
return true;
}
// 找到前半部分链表的尾节点并反转后半部分链表
ListNode firstHalfEnd = endOfFirstHalf(head);
ListNode secondHalfStart = reverseList(firstHalfEnd.next);
// 判断是否回文
ListNode p1 = head;
ListNode p2 = secondHalfStart;
boolean result = true;
while (result && p2 != null) {
if (p1.val != p2.val) {
result = false;
}
p1 = p1.next;
p2 = p2.next;
}
// 还原链表并返回结果
firstHalfEnd.next = reverseList(secondHalfStart);
return result;
}
private ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
private ListNode endOfFirstHalf(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
输入: lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
关键点
- 分治法,两两处理链表
public ListNode mergeKLists(ListNode[] lists) {
return merge(lists, 0, lists.length - 1);
}
public ListNode merge(ListNode[] lists, int l, int r) {
if (l == r) {
return lists[l];
}
if (l > r) {
return null;
}
int mid = (l + r) >> 1;
return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
}
public ListNode mergeTwoLists(ListNode a, ListNode b) {
if (a == null || b == null) {
return a != null ? a : b;
}
ListNode head = new ListNode(0);
ListNode tail = head, aPtr = a, bPtr = b;
while (aPtr != null && bPtr != null) {
if (aPtr.val < bPtr.val) {
tail.next = aPtr;
aPtr = aPtr.next;
} else {
tail.next = bPtr;
bPtr = bPtr.next;
}
tail = tail.next;
}
tail.next = (aPtr != null ? aPtr : bPtr);
return head.next;
}
输入: listA = [4,1,8,4,5], listB = [5,0,1,8,4,5]
输出：8
关键点
- 双指针
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
// 特判
if (headA == null || headB == null) {
return null;
}
ListNode head1 = headA;
ListNode head2 = headB;
while (head1 != head2) {//两个链表走的总路程是相同的,第一个趟长度长的链表多走几步,第二趟就少走几步
if (head1 != null) {
head1 = head1.next;
} else {
head1 = headB;
}
if (head2 != null) {
head2 = head2.next;
} else {
head2 = headA;
}
}
return head1;
}