基本操作
LC21. Merge Two Sorted Lists
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode head = dummy;
while(l1 != null && l2 != null) {
if(l1.val < l2.val){
head.next = l1;
l1 = l1.next;
} else {
head.next = l2;
l2 = l2.next;
}
head = head.next;
}
if (l1 == null) {
head.next = l2;
} else if (l2 == null){
head.next = l1;
}
return dummy.next;
}
链表删除
LC83. Given a sorted linked list, delete all duplicates such that each element appear only once.
Example 1:
Input: 1->1->2
Output: 1->2
public ListNode deleteDuplicates(ListNode head) {
if (head == null || head.next == null) return head;
ListNode cur = head;
while (cur.next != null){
if (cur.val == cur.next.val){
cur.next = cur.next.next;
} else {
cur = cur.next;
}
}
return head;
}
LC82. Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list
Input: 1->1->1->2->3
Output: 2->3
//一般头文件可能被删除的情况可以用dummy来做。
class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prev = dummy;
while (prev.next != null && prev.next.next!= null){
if (prev.next.val == prev.next.next.val){
int val = prev.next.val;
while (prev.next != null && prev.next.val == val)
prev.next = prev.next.next;;// 在这个循环里prev.next永远都是从prev指来的，prev从来没有变过。所以prev.next永远都往下指。
} else {
prev = prev.next;
}
}
return dummy.next;
}
}
LC203. Remove-linked-list-elements
Input: 1->2->6->3->4->5->6, val = 6
Output: 1->2->3->4->5
public ListNode removeElements(ListNode head, int val) {
ListNode root = new ListNode(1);
root.next = head; // next of root is head; ListNode root -> ListNode head
ListNode pre = root; //pre is a pointer, which point to head of new root
while (pre.next != null){
if (pre.next.val == val)
pre.next = pre.next.next;
else {
pre = pre.next;
}
}
return root.next; // alway return the linked list root, not pre. pre is only pointer
}
LC19. Remove Nth Node From End of List
Given a linked list, remove the n-th node from the end of list and return its head.
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.
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode slow = dummy, fast = dummy;
//scan the fast pointer to (n-1)th element
for (int i = 1; i <= n; i++){
fast = fast.next;
}
//move the two pointers together and find the back N element
while(fast.next != null){
fast = fast.next;
slow = slow.next;
}
// delete the required element
slow.next = slow.next.next;
return dummy.next;
}
LC237. Delete Node in a Linked List
Input: head = [4,5,1,9], node = 1
Output: [4,5,9]
Explanation: You are given the third node with value 1, the linked list
should become 4 -> 5 -> 9 after calling your function.
public void deleteNode(ListNode node) {
if (node == null) {
return;
}
node.val = node.next.val;
node.next = node.next.next;
}
链表反转与旋转
LC206 Reverse Linked List
// 1-2-3-4-null
// null-1 2-3-4-null
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null) return null;
ListNode newHead = null;
ListNode temp = null;
while(head != null){
temp = head.next;// create a temp to stroe head.next address(store 2)
head.next = newHead; // head.next can point to prev address after store head.next address(1 point to null)
newHead = head;// prev pointers point to head for next iteration()
head = temp;
}
return newHead;
}
}
LC92. Reverse Linked List II
Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL
public ListNode reverseBetween(ListNode head, int m, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prev = dummy;
for (int i = 1; i < m; i++){
if (prev==null) return null;
prev = prev.next;
}
ListNode premNode = prev;
ListNode mNode = prev.next;
ListNode nNode = mNode;
ListNode postnNode = mNode.next;
for (int i = m; i < n; i++){
if(postnNode == null) return null;
ListNode temp = postnNode.next;
postnNode.next = nNode;
nNode = postnNode;
postnNode = temp;
}
premNode.next = nNode;
mNode.next = postnNode;
return dummy.next;
}
LC24. Swap Nodes in Pairs
Given 1->2->3->4, you should return the list as 2->1->4->3.
public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prev = dummy;
while(prev.next != null && prev.next.next != null){
ListNode temp1 = prev.next; //store 1 address
ListNode temp2 = prev.next.next; // store 2 address
temp1.next = temp2.next;// 1 point to 3
prev.next = temp2; // prev.next point to temp2 address
prev.next.next = temp1;// prev.next.next point to temp1 address
prev = prev.next.next;// prev move to next position for iteration
}
return dummy.next;
}
LC61. Rotate List
Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL
Explanation:
rotate 1 steps to the right: 5->1->2->3->4->NULL
rotate 2 steps to the right: 4->5->1->2->3->NULL
// first we calculate k % length_linkedlist, that is how many elements we would need to move
public ListNode rotateRight(ListNode head, int k) {
if(head == null || head.next == null) return head;
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode fast = dummy;
ListNode slow = dummy;
int i;
for (i = 0; fast.next != null; i++){ // get the whole length of list
fast = fast.next;
}
for (int j = 0; j < i - k % i; j++){
slow = slow.next; // get the partition element;
}
fast.next = dummy.next; //先把dummy.next清空才能放进来
dummy.next = slow.next;
slow.next = null;
return dummy.next;
}
LC24. Swap Nodes in Pairs
Given 1->2->3->4, you should return the list as 2->1->4->3.
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prev = dummy;
while(prev.next != null && prev.next.next != null){
ListNode temp1 = prev.next; //store 1 address
ListNode temp2 = prev.next.next; // store 2 address
temp1.next = temp2.next;// 1 point to 3
prev.next = temp2; // prev.next point to temp2 address
prev.next.next = temp1;// prev.next.next point to temp1 address
prev = prev.next.next;// prev move to next position for iteration
}
return dummy.next;
}
}
LC25. Reverse Nodes in k-Group
Given this linked list: 1->2->3->4->5
For k = 2, you should return: 2->1->4->3->5
For k = 3, you should return: 3->2->1->4->5
LC86. Partition List
Input: head = 1->4->3->2->5->2, x = 3
Output: 1->2->2->4->3->5
public ListNode partition(ListNode head, int x) {
//做两个dummy list，分别判断小于就放左边，大就放右边，最后一步记得把右的next设置为null
if (head == null) return null;
ListNode leftDummy = new ListNode(0);
ListNode rightDummy = new ListNode(0);
ListNode left = leftDummy;
ListNode right = rightDummy;
while(head != null){
if(head.val < x){
left.next = head;
left = left.next;
} else {
right.next = head;
right = right.next;
}
head = head.next;
}
right.next = null;
left.next = rightDummy.next;
return leftDummy.next;
}
LC138. Copy List with Random Pointer
public RandomListNode copyRandomList(RandomListNode head) {
if (head == null) return null;
Map<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>();
// loop 1. copy all the nodes
RandomListNode node = head;
while (node != null) {
map.put(node, new RandomListNode(node.label));
node = node.next;
}
// loop 2. assign next and random pointers
node = head;
while (node != null) {
map.get(node).next = map.get(node.next);
map.get(node).random = map.get(node.random);
node = node.next;
}
return map.get(head);
}
LC141. LinkedList Cycle
public boolean hasCycle(ListNode head) {
ListNode pfast = head;
ListNode pslow = head;
while (pfast != null && pfast.next != null){
pfast = pfast.next.next;
pslow = pslow.next;
if (pfast == pslow){
return true;
}
}
return false;
}
LC141. LinkedList Cycle II
/ 做法就是先判断是不是有环，有环之后，将其中一个指针回到head，和相遇点那个指针一起移动，碰到的地方就是环的起始点。 a+x /1 = a+x+b+x /2 a = b
public class Solution {
public ListNode detectCycle(ListNode head) {
if (head == null || head.next == null) return null;
ListNode fast = head.next;
ListNode slow = head;
while(fast != slow){
if (fast == null || fast.next == null) return null;
fast = fast.next.next;
slow = slow.next;
}
while (head != slow.next){
slow = slow.next;
head = head.next;
}
return head;
}
}
LC143. Reorder List
Given 1->2->3->4, reorder it to 1->4->2->3.
Given 1->2->3->4->5, reorder it to 1->5->2->4->3.
// 先找到中点，再把中点后的reverse一下,最后merge
class Solution {
public void reorderList(ListNode head) {
if (head == null) return ; // notice 边界条件
ListNode middle = findMiddle(head);
ListNode left = reverse(middle.next);
middle.next = null;//断开连接
ListNode right = head;
merge(right, left);
}
private ListNode reverse(ListNode head){
ListNode prev = null;
while (head != null){
ListNode temp = head.next;
head.next = prev;
prev = head;
head = temp;
}
return prev;
}
private ListNode findMiddle(ListNode head){
ListNode slow = head;
ListNode fast = head.next;
while (fast != null && fast.next!= null){
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
private ListNode merge(ListNode l1, ListNode l2){
ListNode dummy = new ListNode(0);
ListNode head = dummy;
int count = 1;
while (l1 != null && l2 !=null){
if(count % 2 != 0){
head.next = l1;
l1 = l1.next;
} else {
head.next = l2;
l2 = l2.next;
}
head = head.next;
count++;
}
if (l1 != null){
head.next = l1;
} else if (l2 != null){
head.next = l2;
}
return dummy.next;
}
}
LC148. Sort List
Input: 4->2->1->3
Output: 1->2->3->4
public ListNode sortList(ListNode head) {
if(head == null || head.next == null) return head;
ListNode mid = findMiddle(head);
ListNode right = sortList(mid.next);
mid.next = null;//此处是为了让右半边的链表断开到mid结束。
ListNode left = sortList(head);
return merge(left, right);
}
// find middle point
private ListNode findMiddle(ListNode head){
ListNode slow = head;
ListNode fast = head.next;
while (fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;// 当出现..next时候，前两个必须一一判断是否为空
}
return slow;
}
// merge sorting list
private ListNode merge(ListNode l1, ListNode l2){
ListNode dummy = new ListNode(0);
ListNode head = dummy;
while (l1 != null && l2 != null){
if (l1.val < l2.val){
head.next = l1;
l1 = l1.next;
} else {
head.next = l2;
l2 = l2.next;
}
head = head.next;
}
if (l1 != null){
head.next = l1;
} else if (l2 != null){
head.next = l2;
}
return dummy.next;
}
LC328. Odd Even Linked List
Input: 2->1->3->5->6->4->7->NULL
Output: 2->3->6->7->1->5->4->NULL
public ListNode oddEvenList(ListNode head) {
if (head == null) return null;
ListNode odd = head;
ListNode even = head.next;
ListNode evenH = even;
while (even != null && even.next != null){
odd.next = odd.next.next;//有顺序的不然地址会丢失。
even.next = even.next.next;
even = even.next;
odd = odd.next;
}
odd.next = evenH;
return head;
}
LC160. Intersection of Two Linked
A: a1 → a2
↘
c1 → c2 → c3
↗
B: b1 → b2 → b3
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null){
return null;
}
int lenA= getLength(headA), lenB= getLength(headB);
if (lenA > lenB) {
for (int i =0; i< lenA - lenB; i++) headA = headA.next;
} else {
for (int i =0; i< lenB - lenA; i++) headB = headB.next;
}
while (headA != null && headB != null && headA != headB){
headA = headA.next;
headB = headB.next;
}
if (headA != null && headB != null){
return headA;
} else {
return null;
}
}
public int getLength(ListNode head){
int count = 0;
while (head != null){
count++;
head = head.next;
}
return count;
}
LC234. Palindrome Linked List
Input: 1->2->2->1
Output: true
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) return true;
ListNode slow = head;
ListNode fast = head;
/*find middle point of liked list*/
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){
ListNode p = head, newHead = null;
while (p!= null){
ListNode temp = p.next;
p.next = newHead;
newHead = p;
p = temp;
}
return newHead;
}
