@Yano
2015-12-30T03:23:34.000000Z
字数 11605
阅读 13986
LeetCode
我的博客：http://blog.csdn.net/yano_nankai
LeetCode题解：https://github.com/LjyYano/LeetCode
LeetCode之Array题目汇总
LeetCode之Hash Table题目汇总
LeetCode之Linked List题目汇总
LeetCode之Math题目汇总
LeetCode之String题目汇总
LeetCode之Binary Search题目汇总
LeetCode之Divide and Conquer题目汇总
LeetCode之Dynamic Programming题目汇总
LeetCode之Backtracing题目汇总
LeetCode之Stack题目汇总
LeetCode之Sort题目汇总
LeetCode之Bit Manipulation题目汇总
LeetCode之Tree题目汇总
LeetCode之Depth-first Search题目汇总
LeetCode之Breadth-first Search题目汇总
LeetCode之Graph题目汇总
LeetCode之Trie题目汇总
LeetCode之Design题目汇总
文章目录：
You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
if (l1 == null && l2 == null) {
return null;
}
if (l1 == null) {
return l2;
}
if (l2 == null) {
return l1;
}
ListNode p1 = l1;
ListNode p2 = l2;
int carry = 0;
ListNode head = new ListNode(0);
ListNode result = head;
while (carry != 0 || p1 != null || p2 != null) {
int v1 = 0;
if (p1 != null) {
v1 = p1.val;
p1 = p1.next;
}
int v2 = 0;
if (p2 != null) {
v2 = p2.val;
p2 = p2.next;
}
int tmp = v1 + v2 + carry;
carry = tmp / 10;
head.next = new ListNode(tmp % 10);
head = head.next;
}
return result.next;
}
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
参考：LeetCode 108 Convert Sorted Array to Binary Search Tree
但是不能将linked list转换成arraylist，会超时。思路：快慢指针。
ListNode cutAtMid(ListNode head) {
if (head == null) {
return null;
}
ListNode fast = head;
ListNode slow = head;
ListNode pslow = head;
while (fast != null && fast.next != null) {
pslow = slow;
slow = slow.next;
fast = fast.next.next;
}
pslow.next = null;
return slow;
}
public TreeNode sortedListToBST(ListNode head) {
if (head == null) {
return null;
}
if (head.next == null) {
return new TreeNode(head.val);
}
ListNode mid = cutAtMid(head);
TreeNode root = new TreeNode(mid.val);
root.left = sortedListToBST(head);
root.right = sortedListToBST(mid.next);
return root;
}
Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.
Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with value 3, the linked list should become 1 -> 2 -> 4 after calling your function.
题目是让删除链表中的指定结点，这个结点不是尾结点。
要求时间复杂度是O(1)
我们通常的想法是：要删除链表的一个结点node，必须找到node的前驱结点pre，使用pre.next = node.next才能删除。但是单链表不遍历的话，是无法找到pre的，所以时间复杂度是O(n)。
要删除node，我们为什么不利用后继结点succ呢？
我们可以把succ的值复制到node中，然后删除succ！
public void deleteNode(ListNode node) {
if (node == null) {
return;
}
node.val = node.next.val;
node.next = node.next.next;
}
Sort a linked list using insertion sort.
public ListNode insertionSortList(ListNode head) {
if (head == null)
return null;
if (head.next == null)
return head;
final ListNode _head = new ListNode(Integer.MIN_VALUE);
_head.next = head;
head = head.next;
_head.next.next = null;
next: while (head != null) {
ListNode taken = head;
head = head.next;
ListNode cur = _head.next;
ListNode last = _head;
while (cur != null) {
if (cur.val > taken.val) {
// insert
last.next = taken;
taken.next = cur;
continue next;
}
cur = cur.next;
last = last.next;
}
last.next = taken;
taken.next = null;
}
return _head.next;
}
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:
null.Credits:
Special thanks to @stellari for adding this problem and creating all test cases.
记链表A的长度是lenA，最后一个结点为p；链表B的长度是lenB，最后一个结点为q。
如果p≠q，则链表A、B不相交，直接返回null。因为如果链表A、B在某处相交，那么后面的结点完全相同（如题目中所示，是Y型的）。
如果p=q，则链表A、B在某处相交。让长的链表走|lenA−lenB|步（按照末端对齐），然后两个链表同时向前走，相等结点即为相交公共结点。
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
// 计算链表A的长度
int lenA = 1;
ListNode p = headA;
while (p.next != null) {
lenA++;
p = p.next;
}
// 计算链表B的长度
int lenB = 1;
ListNode q = headB;
while (q.next != null) {
lenB++;
q = q.next;
}
// 若A和B的最后一个结点不等，则不相交，返回null
if (p != q) {
return null;
}
// 链表按照尾部对齐
if (lenA > lenB) {
int t = lenA - lenB;
while (t-- != 0) {
headA = headA.next;
}
} else {
int t = lenB - lenA;
while (t-- != 0) {
headB = headB.next;
}
}
// 同时向前走
while (headA != headB) {
headA = headA.next;
headB = headB.next;
}
return headA;
}
Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space?
快慢指针，定义两个指针，一个每次走一步，另一个每次走两步。如果快指针“遇到”了慢指针，说明有环。
public boolean hasCycle(ListNode head) {
if (head == null) {
return false;
}
ListNode slow = head;
ListNode fast = head.next;
while (fast != null) {
if (fast.next == null || fast.next.next == null) {
return false;
}
if (slow == fast) {
return true;
}
fast = fast.next.next;
slow = slow.next;
}
return false;
}
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
Note: Do not modify the linked list.
Follow up:
Can you solve it without using extra space?
以下参考：[原]求单链表环的入口结点 Linked List Cycle II
slow指针每次走1步，fast指针每次走2步。如果链表有环，那么两个指针一定会相遇。
设链表头到环入口结点的结点数目是a，环内的结点数目r。假设相遇时，fast指针已经绕环转了n圈，比slow多走了n*r步。假设环的入口结点到相遇结点的结点数目为x。
那么在相遇时，slow走了a+x步，fast走了a+x+n*r步。
由于fast的步调是slow的两倍，所以有a+x = n*r。因而，a = n*r - x
显然，从相遇位置开始，走n*r - x步，一定可以到达环的入口结点；从链表头开始，走a步，也会到达环的入口。并且我们得到了a = n*r - x。所以我们让两个指针，一个从相遇位置出发一个从链表头出发，让他们都单步前进。因为a = n*r - x，所以他们一定会在环的入口相遇。
public ListNode detectCycle(ListNode head) {
if (head == null) {
return null;
}
ListNode slow = head;
ListNode fast = head.next;
boolean meet = false;
int len = 0;
// 判断是否有环，并计数
while (fast != null) {
if (fast.next == null || fast.next.next == null) {
return null;
}
if (slow == fast) {
if (meet) {
break;
}
meet = true;
}
fast = fast.next.next;
slow = slow.next;
if (meet) {
len++;
}
}
if (meet) {
slow = head;
fast = head;
// fast先走len步
for (int i = 0; i < len; i++) {
fast = fast.next;
}
// slow从起始点出发，fast从len处出发
// 二者相遇的结点，即为入环结点
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
return null;
}
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null && l2 == null) {
return null;
}
if (l1 == null) {
return l2;
}
if (l2 == null) {
return l1;
}
ListNode p = new ListNode(0);
ListNode head = p;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
p.next = l1;
l1 = l1.next;
} else {
p.next = l2;
l2 = l2.next;
}
p = p.next;
}
if (l1 != null) {
p.next = l1;
} else {
p.next = l2;
}
return head.next;
}
Given a singly linked list, determine if it is a palindrome.
Follow up:
Could you do it in O(n) time and O(1) space?
O(n) time and O(1) space的解法：
说明：不用管链表是奇数还是偶数，如果链表长度是偶数，那么翻转后，前段和后段链表长度相等；如果是奇数，后段链表长1个结点，所以只需要判断前段结点是否遍历结束。
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) {
return true;
}
ListNode slow = head;
ListNode fast = head;
// 找到链表中点
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// 翻转后段链表
ListNode tail = reverseList(slow);
while (head != slow) {
if (head.val != tail.val) {
return false;
}
head = head.next;
tail = tail.next;
}
return true;
}
public ListNode reverseList(ListNode head) {
if (head == null) {
return null;
}
if (head.next == null) {
return head;
}
ListNode tail = head.next;
ListNode reversed = reverseList(head.next);
// 前后翻转tail和head
tail.next = head;
head.next = null;
return reversed;
}
Given a sorted linked list, delete all duplicates such that each element appear only once.
For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.
public ListNode deleteDuplicates(ListNode head) {
if (head == null) {
return null;
}
if (head.next == null) {
return head;
}
ListNode node = head;
while (node.next != null) {
// 如果元素不重复，跳过
if (node.val != node.next.val) {
node = node.next;
} else {
// 重复，则跳过下一个
while (node.next != null && node.val == node.next.val) {
node.next = node.next.next;
}
}
}
return head;
}
Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.
public ListNode deleteDuplicates(ListNode head) {
if (head == null) {
return null;
}
if (head.next == null) {
return head;
}
int val = head.val;
ListNode node = head;
boolean killme = false;
while (node.next != null && node.next.val == val) {
node = node.next;
killme = true;
}
if (killme) {
head = deleteDuplicates(node.next);
} else {
head.next = deleteDuplicates(node.next);
}
return head;
}
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.
题目中说n是合法的，就不用对n进行检查了。用标尺的思想，两个指针相距为n-1，后一个到表尾，则前一个到n了。(p为second，q为first)
删除p。
public ListNode removeNthFromEnd(ListNode head, int n) {
if (head == null || head.next == null) {
return null;
}
ListNode first = head;
ListNode second = head;
for (int i = 0; i < n; i++) {
first = first.next;
if (first == null) {
return head.next;
}
}
while (first.next != null) {
first = first.next;
second = second.next;
}
second.next = second.next.next;
return head;
}
Reverse a singly linked list.
Hint:
A linked list can be reversed either iteratively or recursively. Could you implement both?
public ListNode reverseList(ListNode head) {
if (head == null) {
return null;
}
if (head.next == null) {
return head;
}
ListNode tail = head.next;
ListNode reversed = reverseList(head.next);
// 前后翻转tail和head
tail.next = head;
head.next = null;
return reversed;
}
Reverse a linked list from position m to n. Do it in-place and in one-pass.
For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,
return 1->4->3->2->5->NULL.
Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.
public ListNode reverseBetween(ListNode head, int m, int n) {
if (head == null || head.next == null || m == n) {
return head;
}
ListNode fakeHead = new ListNode(-1);
fakeHead.next = head;
// 先向后移m步
ListNode pre = fakeHead;
for (int i = 1; i < m; i++) {
pre = pre.next;
}
// 对后面的n-m个结点，逆置
ListNode mNode = pre.next;
for (int i = m; i < n; i++) {
ListNode cur = mNode.next;
mNode.next = cur.next;
cur.next = pre.next;
pre.next = cur;
}
return fakeHead.next;
}
Given a list, rotate the list to the right by k places, where k is non-negative.
For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.
public ListNode rotateRight(ListNode head, int k) {
if (head == null)
return null;
int len = 1;
ListNode tail = head;
while (tail.next != null) {
len++;
tail = tail.next;
}
tail.next = head; // cycle
k %= len;
for (int i = 1; i < len - k; i++) {
head = head.next;
}
try {
return head.next;
} finally {
head.next = null; // cut
}
}
Sort a linked list in O(n log n) time using constant space complexity.
O(n log n) 的时间复杂度，归并排序最好，因为它不会因为输入序列的基本有序而变化。
参考：LeetCode 021 Merge Two Sorted Lists
LeetCode 021 Merge Two Sorted Lists
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode rt = new ListNode(0);
ListNode h = rt;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
rt.next = l1;
l1 = l1.next;
} else {
rt.next = l2;
l2 = l2.next;
}
rt = rt.next;
}
if (l1 != null)
rt.next = l1;
else
rt.next = l2;
return h.next;
}
public ListNode sortList(ListNode head) {
if (head == null)
return null;
if (head.next == null)
return head;
ListNode fast = head.next;
ListNode slow = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode h2 = slow.next;
slow.next = null;
return mergeTwoLists(sortList(head), sortList(h2));
}
Given a linked list, swap every two adjacent nodes and return its head.
For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.
Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.
public ListNode swapPairs(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode fakeHead = new ListNode(0);
fakeHead.next = head;
ListNode p1 = fakeHead;
ListNode p2 = head;
while (p2 != null && p2.next != null) {
ListNode nextStart = p2.next.next;
p2.next.next = p2;
p1.next = p2.next;
p2.next = nextStart;
p1 = p2;
p2 = p2.next;
}
return fakeHead.next;
}