@Yano 2015-12-30T03:23:34.000000Z 字数 11605 阅读 13026

LeetCode

LeetCode 题目汇总

# Add Two Numbers

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);
}

return result.next;
}


# Convert Sorted List to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

    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) {
}

ListNode mid = cutAtMid(head);

TreeNode root = new TreeNode(mid.val);
root.right = sortedListToBST(mid.next);

return root;
}


# Delete Node in a Linked List

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.

    public void deleteNode(ListNode node) {

if (node == null) {
return;
}

node.val = node.next.val;
node.next = node.next.next;
}


# Insertion Sort List

Sort a linked list using insertion sort.

    public ListNode insertionSortList(ListNode head) {

if (head == null)
return null;
if (head.next == null)

final ListNode _head = new ListNode(Integer.MIN_VALUE);

next: while (head != null) {

ListNode taken = head;

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;

}

}


# 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.

Credits:
Special thanks to @stellari for adding this problem and creating all test cases.

1. 记链表A的长度是lenA，最后一个结点为p；链表B的长度是lenB，最后一个结点为q。

2. 如果p≠q，则链表A、B不相交，直接返回null。因为如果链表A、B在某处相交，那么后面的结点完全相同（如题目中所示，是Y型的）。

3. 如果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) {
}
} else {
int t = lenB - lenA;
while (t-- != 0) {
}
}

// 同时向前走
}

}


# Linked List Cycle

Given a linked list, determine if it has a cycle in it.

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;
}


# Linked List Cycle II

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.

Can you solve it without using extra space?

slow指针每次走1步，fast指针每次走2步。如果链表有环，那么两个指针一定会相遇。

    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) {

// 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 Lists

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;
}

}


# Palindrome Linked List

Given a singly linked list, determine if it is a palindrome.

Could you do it in O(n) time and O(1) space?

O(n) time and O(1) space的解法：

1. 找到链表中点
2. 将后半段链表翻转
3. 对比两段链表

    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;
}
tail = tail.next;
}

return true;
}

public ListNode reverseList(ListNode head) {

if (head == null) {
return null;
}

if (head.next == null) {
}

ListNode tail = head.next;
ListNode reversed = reverseList(head.next);

return reversed;

}


# Remove Duplicates from Sorted List

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) {
}

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;
}
}
}

}


# Remove Duplicates from Sorted List II

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) {
}

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) {
} else {
}

}


# 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.

1. 指针p、q指向链表头部；
2. 移动q，使p和q差n-1；
3. 同时移动p和q，使q到表尾；
4. 删除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) {
}
}

while (first.next != null) {
first = first.next;
second = second.next;
}

second.next = second.next.next;

}


# Reverse Linked List

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) {
}

ListNode tail = head.next;
ListNode reversed = reverseList(head.next);

return reversed;
}


# Reverse Linked List II

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->NULLm = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note:
Given mn 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) {
}

ListNode fakeHead = new ListNode(-1);

// 先向后移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;
}

}


# Rotate List

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++) {
}

try {
} finally {
head.next = null; // cut
}
}


# Sort List

Sort a linked list in O(n log n) time using constant space complexity.

O(n log n) 的时间复杂度，归并排序最好，因为它不会因为输入序列的基本有序而变化。

1. 首先将List分成两个
2. MergeSort(left) ，MegerSort(right)
3. 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)

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;

}


# Swap Nodes in Pairs

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) {
}

ListNode fakeHead = new ListNode(0);

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;
}