翻转链表
迭代实现较为容易, 一般要用dummy做一个虚拟头指针, 因为头结点可能会变, 这里主要用来理解递归的方向来做. 我把base条件叫做终极情况, 这个终极情况是退出递归的最小子问题, 而次小子问题是极限情况, 也就是功能区的代码. 翻转链表一般都是后序遍历的思想, 函数的功能就是返回前一个子问题的答案.
206. 反转链表
和<236.二叉树的最近公共祖先>类似, 因为要从最后一个点往前翻, 所以相当于一个简化的后序遍历. reverseList的功能是返回反转后链表的头, 功能区仅考虑极限情况. 如2->3->1->5, 极限情况就是head为1, head.next为5. 而终极情况是base case, 也就是if (head == null || head.next == null) return head;. head.next就相当于treenode.right, 这道题可以简化地看成后序遍历. h的目的是取最后一个结点作为新的头结点. head才完成真正的翻转功能.
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode h = reverseList(head.next);
//极限情况 post
head.next.next = head;
head.next = null;
return h;
}
}
92. 反转链表II
控制范围, 两个index要同时减小.
class Solution {
ListNode successor = null;
public ListNode reverseBetween(ListNode head, int left, int right) {
if (left == 1) return reverseBetween(head, right);
head.next = reverseBetween(head.next, left - 1, right - 1);
return head;
}
public ListNode reverseBetween(ListNode head, int right) {
if (right == 1) {
successor = head.next;
return head;
}
ListNode h = reverseBetween(head.next, right - 1);
head.next.next = head;
head.next = successor;
return h;
}
}
迭代法.
class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
if (head == null) return head;
ListNode cur = head, pre = null;
while (left > 1) {
pre = cur;
cur = cur.next;
left--;
right--;
}
ListNode second_head = pre, tail = cur;
while (right > 0) {
ListNode temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
right--;
}
if (second_head != null) second_head.next = pre;
else head = pre;
tail.next = cur;
return head;
}
}
24. 两两交换链表中的节点
交换依然是从后往前的, 那么类似后序遍历. 函数功能是返回反转后子pair的头. 举例, 1->2->3->4翻转成2->1->4->3极限条件是翻转4->3, 4就是新的头node, node.next指向head. 而head.next应该指向head.next.next, 也就是老的头指向子pair新的头. 对于终极情况来说, 就是指向null.
class Solution {
public ListNode swapPairs(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode newHead = head.next;
head.next = swapPairs(newHead.next);
newHead.next = head;
return newHead;
}
}
25. K个一组翻转链表
这道题递归就不好做了, 用迭代. 拆分问题, 先实现ListNode reverse(ListNode a, ListNode b), 完成两个结点之间的翻转, 再k个一组去翻转.
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
ListNode a = head, b = head;
for (int i = 0; i < k; i++) {
if (b == null) return head;
b = b.next;
}
ListNode newHead = reverse(a, b);
a.next = reverseKGroup(b, k);
return newHead;
}
public ListNode reverse(ListNode a, ListNode b) {
ListNode pre = null, cur = a;
while (cur != b) {
ListNode temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
}
return pre;
}
}
双指针
这种题做的时候要画图, 注意边界条件, 要改变head节点的时候就用dummy的虚拟节点指向它, 最后返回dummy.next即可.
19. 删除链表的倒数第N个节点
经典双指针.
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode();
dummy.next = head;
ListNode left = dummy;
ListNode right = dummy;
for (int i = 0; i < n; i++) right = right.next;
while (right != null && right.next != null) {
left = left.next;
right = right.next;
}
left.next = left.next.next;
return dummy.next;
}
}
160. 相交链表
两个指向头指针的node不断向后跑, A出发的node跑完后再指向B的头继续跑, B出发的node跑完后再指向A的头继续跑, 这两个node必然在相交的地方相遇, 因为总路程一样.
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) return null;
ListNode nodeA = headA, nodeB = headB;
while (nodeA != nodeB) {
if (nodeA == null) nodeA = headB;
if (nodeB == null) nodeB = headA;
if (nodeA == nodeB) return nodeA;
nodeA = nodeA.next;
nodeB = nodeB.next;
}
return nodeA;
}
}
141. 环形链表
快慢指针, 如果有环那么慢指针在环里面一定会被快指针追上.
public class Solution {
public boolean hasCycle(ListNode head) {
if (head == null) return false;
ListNode slow = head, fast = head.next;
while (slow != fast) {
slow = slow.next;
if (fast == null || fast.next == null) return false;
fast = fast.next.next;
}
return true;
}
}
142. 环形链表II
快慢指针同时出发, 快指针走的路程始终是慢指针的两倍, 那么如果非环的长度是x, 当慢指针到入环的第一个节点时, 快指针已经在环中走了x步, 如果这个时候还差y步到入环的第一个节点, 快慢指针再次相遇时快指针也会多走y步, 也就是说这个时候两个指针都指针差x步到入环的第一个节点. 那么在这个时候, 用新的指针指向head, 和slow一起移动x步即可, 最后指针会在入环的节点相遇.
public class Solution {
public ListNode detectCycle(ListNode head) {
if (head == null) return null;
ListNode slow = head, fast = head;
while (fast != null) {
slow = slow.next;
if (fast.next != null) {
fast = fast.next.next;
} else {
return null;
}
if (fast == slow) {
fast = head;
while (fast != slow) {
fast = fast.next;
slow = slow.next;
}
return fast;
}
}
return null;
}
}
排序
147. 对链表进行插入排序
用last指向已排序的最后一个数
class Solution {
public ListNode insertionSortList(ListNode head) {
if (head == null) return head;
ListNode dummy = new ListNode();
dummy.next = head;
ListNode cur = head.next, last = head;
while (cur != null) {
if (cur.val >= last.val) {
last = last.next;
} else {
ListNode node = dummy;
while (cur.val >= node.next.val) node = node.next;
last.next = cur.next; //断掉cur
cur.next = node.next; //cur放前面去
node.next = cur; //连接cur的前一个节点
}
cur = last.next;
}
return dummy.next;
}
}
148. 排序链表
归并链表版.
class Solution {
public ListNode sortList(ListNode head) {
return mergeSort(head, null);
}
public ListNode mergeSort(ListNode head, ListNode tail) {
if (head == null) return head;
if (head.next == tail) {
head.next = null;
return head;
}
ListNode slow = head, fast = head;
while (fast != tail) {
slow = slow.next;
fast = fast.next;
if (fast != tail) fast = fast.next;
}
ListNode mid = slow;
ListNode list1 = mergeSort(head, mid);
ListNode list2 = mergeSort(mid, tail);
ListNode sorted = merge(list1, list2);
return sorted;
}
public ListNode merge(ListNode head1, ListNode head2) {
ListNode dummy = new ListNode(0);
ListNode temp = dummy, left = head1, right = head2;
while (left != null && right != null) {
if (left.val <= right.val) {
temp.next = left;
left = left.next;
} else {
temp.next = right;
right = right.next;
}
temp = temp.next;
}
if (left != null) temp.next = left;
if (right != null) temp.next = right;
return dummy.next;
}
}
其他
237. 删除链表中的节点
做多了题这倒容易迷惑, 实际上就是简单的赋值再删除.
class Solution {
public void deleteNode(ListNode node) {
node.val = node.next.val;
node.next = node.next.next;
}
}
83. 删除排序链表中的重复元素
class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode node = head;
while (node != null) {
while (node.next != null && node.val == node.next.val) {
node.next = node.next.next;
}
node = node.next;
}
return head;
}
}
61. 旋转链表
拼一拼, 注意输入可能为null.
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if (head == null) return head;
ListNode tail = head;
int len = 0;
while (tail.next != null) {
tail = tail.next;
len++;
}
len += 1;
k = k % len;
if (k == 0) return head;
tail.next = head;
ListNode node = head;
for (int i = 0; i < len - k - 1; i++) {
node = node.next;
}
ListNode res = node.next;
node.next = null;
return res;
}
}
参考
comments powered by Disqus