CyC2018
1、找到两个链表相交的点，L160
// 思路: a + c + b = b + c + a
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode p1 = headA;
ListNode p2 = headB;
while(p1 != p2) {
p1 = p1 == null ? headB : p1.next;
p2 = p2 == null ? headA : p2.next;
}
return p1;
}
}
2、链表反转，L206
// 思路：利用循环指针去反转链表，一个个链接反转
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null) return null;
ListNode pre = null;
ListNode cur = head;
while (cur.next != null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
cur.next = pre;
return cur;
}
}
// 思路：递归处理
class Solution1 {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode ret = reverseList(head.next);
head.next.next = head;
head.next = null;
return ret;
}
}
3、归并两个有序的链表，L21
// 思路：递归
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null)
return l2;
if (l2 == null)
return l1;
if (l1.val > l2.val) {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
} else {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
}
}
}
// 思路：迭代，用两个循环变量指针，和一个指向合并结果的指针作为循环变量
class Solution1 {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) return l2;
if (l2 == null) return l1;
ListNode res = new ListNode(-1);
ListNode p = res;
while (l1 != null && l2 != null) {
if (l1.val > l2.val) {
p.next = l2;
l2 = l2.next;
} else {
p.next = l1;
l1 = l1.next;
}
p = p.next;
}
if (l1 != null) p.next = l1;
if (l2 != null) p.next = l2;
return res.next;
}
}
4、从有序链表中删除重复节点，L83
// 用pre慢指针和快指针做比较，判断是否相等
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (head == null) return head;
ListNode pre = head;
ListNode p = head.next;
while (p != null) {
if (p.val == pre.val) {
pre.next = p.next;
} else {
pre = p;
}
p = p.next;
}
return head;
}
}
// 思路：递归
class Solution1 {
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、删除链表的倒数第 n 个节点，L19
// 思路：用快慢指针，快指针比满指针快n步，当fast.next == null时，说明slow指向倒数前n个指针的前一个
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode fast = head;
while (n-- > 0) {
fast = fast.next;
}
if (fast == null) {
return head.next;
}
ListNode slow = head;
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return head;
}
}
6、交换链表中的相邻结点，L24
// 注意要考虑前一个节点，设立一个虚头结点作为最开始的pre指针，并以此为循环变量
class Solution {
public ListNode swapPairs(ListNode head) {
if (head == null || head.next == null) return head;
ListNode newHead = new ListNode(-1);
newHead.next = head;
ListNode pre = newHead;
while (pre.next != null && pre.next.next != null) {
ListNode l1 = pre.next;
ListNode l2 = pre.next.next;
l1.next = l2.next;
l2.next = l1;
pre.next = l2;
pre = l1;
}
return newHead.next;
}
}
7、链表求和，L445
// 先反转列表然后在运算，得到结果在反转，比用栈快
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
l1 = reverseList(l1);
l2 = reverseList(l2);
int carry = 0;
ListNode newHead = new ListNode(-1);
ListNode p = newHead;
while (l1 != null || l2 != null || carry != 0) {
int x = 0;
int y = 0;
if (l1 != null) {
x = l1.val;
l1 = l1.next;
}
if (l2 != null) {
y = l2.val;
l2 = l2.next;
}
int sum = x + y + carry;
ListNode newNode = new ListNode(sum % 10);
p.next = newNode;
p = p.next;
carry = sum / 10;
}
return reverseList(newHead.next);
}
public ListNode reverseList(ListNode head) {
if (head == null) return null;
ListNode pre = null;
ListNode cur = head;
while (cur.next != null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
cur.next = pre;
return cur;
}
}
8、回文链表，L234
// 快慢指针，然后反转后半部分进行比较，注意快慢指针的起始值，快慢指针效率最高
class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) return true;
ListNode fast = head.next;
ListNode slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
slow = slow.next;
ListNode newHead = reverseList(slow);
while (newHead != null) {
if (newHead.val != head.val) return false;
head = head.next;
newHead = newHead.next;
}
return true;
}
public ListNode reverseList(ListNode head) {
ListNode newHead = new ListNode(-1);
while (head != null) {
ListNode next = head.next;
head.next = newHead.next;
newHead.next = head;
head = next;
}
return newHead.next;
}
}
// 递归解法二，用类变量记录
class Solution2 {
private ListNode front;
public boolean isPalindrome(ListNode head) {
front = head;
return palindrome(head);
}
public boolean palindrome(ListNode curNode) {
if (curNode != null) {
if (!palindrome(curNode.next)) {
return false;
}
if (curNode.val != front.val) {
return false;
}
front = front.next;
}
return true;
}
}
// 递归解法，很巧妙，不用反转列表，但是时间和空间效率不高
class Solution1 {
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) {
return true;
}
ListNode newHead = new ListNode(-1);
newHead.next = head;
return palindromeList(head, newHead);
}
public boolean palindromeList(ListNode h1, ListNode h2) {
if (h1 == null) {
return true;
}
boolean first = palindromeList(h1.next, h2);
boolean second;
if (h1.val == h2.next.val) {
second = true;
h2.next = h2.next.next;
} else {
second = false;
}
return second && first;
}
}
9、分隔链表，L725
// 优化循环，注意最后切断的时候置为null
class Solution {
public ListNode[] splitListToParts(ListNode head, int k) {
ListNode[] res = new ListNode[k];
ListNode p = head;
int length = 0;
while (p != null) {
length++;
p = p.next;
}
int size = length / k;
int mod = length % k;
for (int i = 0; i < k && head != null; i++) {
int curSize = size + (mod-- > 0 ? 1 : 0);
res[i] = head;
for (int j = 1; j < curSize; j++) {
head = head.next;
}
ListNode next = head.next;
head.next = null;
head = next;
}
return res;
}
}
10、链表元素按奇偶聚集，L328
// 记录odd，even的尾指针
class Solution {
public ListNode oddEvenList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode odd = head;
ListNode even = head.next;
ListNode evenHead = even;
while (even != null && even.next != null) {
odd.next = odd.next.next;
even.next = even.next.next;
odd = odd.next;
even = even.next;
}
odd.next = evenHead;
return head;
}
}
Carl
1、移除链表中的元素，L203
// 迭代实现
class Solution {
public ListNode removeElements(ListNode head, int val) {
ListNode newHead = new ListNode(-1);
newHead.next = head;
ListNode p = newHead;
while (p != null && p.next != null) {
if (p.next.val == val) {
p.next = p.next.next;
} else {
p = p.next;
}
}
return newHead.next;
}
}
// 递归
class Solution {
public ListNode removeElements(ListNode head, int val) {
if (head == null) return null;
head.next = removeElements(head.next, val);
return head.val == val ? head.next : head;
}
}
2、环形链表入口，L142
public class Solution {
public ListNode detectCycle(ListNode head) {
if (head == null || head.next == null) return null;
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
ListNode p = head;
while (p != fast) {
p = p.next;
fast = fast.next;
}
return fast;
}
}
return null;
}
}
