203. Remove Linked List Elements
Solved
Easy
Topics
Companies
Given the head of a linked list and an integer val, remove all the nodes of the linked list that has Node.val == val, and return the new head.
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeElements(ListNode head, int val) {
ListNode dummyHead = new ListNode(-1,head);
ListNode cur = dummyHead;
while(cur != null && cur.next != null){
if(cur.next.val == val){
cur.next = cur.next.next;
}else{
cur = cur.next;
}
}
return dummyHead.next;
}
}Solved
Easy
Topics
Companies
Given the head of a singly linked list, reverse the list, and return the reversed list.
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
ListNode newHead = null;
ListNode o1 = head;
while(o1 != null){
ListNode o2 = o1.next;
o1.next = newHead;
newHead = o1;
o1 = o2;
}
return newHead;
}
}/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode last = reverseList(head.next);
head.next.next = head;
head.next = null;
return last;
}
}Solved
Medium
Topics
Companies
Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed.)
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummyHead = new ListNode(-1 , head);
ListNode cur = dummyHead;
ListNode n1 = head;
while(n1 != null && n1.next != null){
ListNode n2 = n1.next.next;
cur.next = n1.next;
n1.next.next = n1;
n1.next = n2;
cur = n1;
n1 = n2;
}
return dummyHead.next;
}
}/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
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;
}
}
19. Remove Nth Node From End of List
Solved
Medium
Topics
Companies
Hint
Given the head of a linked list, remove the nth node from the end of the list and return its head.
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummyHead = new ListNode(-1, head);
ListNode n1 = dummyHead;
ListNode n2 = dummyHead;
for(int i = 0; i < n + 1; i++){
n2 = n2.next;
}
while(n2 != null){
n2 = n2.next;
n1 = n1.next;
}
n1.next = n1.next.next;
return dummyHead.next;
}
}Easy
Given head, the head of a linked list, determine if the linked list has a cycle in it.
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.
Return true if there is a cycle in the linked list. Otherwise, return false.
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) {
return false;
}
ListNode slow = head;
ListNode fast = head.next;
while(fast!=null && fast.next!=null){
if(slow == fast) return true;
slow=slow.next;
fast=fast.next.next;
}
return false;
}
}Solved
Medium
Topics
Companies
Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to (0-indexed). It is -1 if there is no cycle. Note that pos is not passed as a parameter.
Do not modify the linked list.
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
if(head==null){
return null;
}
ListNode fast = head;
ListNode slow =head;
while(fast!=null && fast.next!=null){
fast = fast.next.next;
slow = slow.next;
if(slow == fast){
slow = head;
while(slow!=fast){
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
return null;
}
}Solved
Easy
Topics
Companies
You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.
Return the head of the merged linked list.
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode dummyHead = new ListNode(-1,null);
ListNode n = dummyHead;
while (list1 != null && list2 != null) {
if (list1.val < list2.val) {
n.next = list1;
list1 = list1.next;
} else {
n.next = list2;
list2 = list2.next;
}
n = n.next;
}
if (list1 == null) {
n.next = list2;
}
if (list2 == null) {
n.next = list1;
}
return dummyHead.next;
}
}82. Remove Duplicates from Sorted List II
Solved
Medium
Topics
Companies
Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted as well.
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode dummyHead = new ListNode(-1 , head);
ListNode slow = dummyHead;
ListNode fast = head;
while(fast != null && fast.next != null){
if(fast.val == fast.next.val){
int val = fast.val;
while(fast != null && fast.val == val){
fast = fast.next;
slow.next = fast;
}
}else{
fast = fast.next;
slow = slow.next;
}
}
return dummyHead.next;
}
}/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode dummyHead = new ListNode(-1, head);
ListNode cur = dummyHead;
while (cur.next != null && cur.next.next != null) {
if (cur.next.val == cur.next.next.val) {
ListNode p = cur.next;
while (cur.next != null && cur.next.val == p.val) {
cur.next = cur.next.next;
}
} else {
cur = cur.next;
}
}
return dummyHead.next;
}
}83. Remove Duplicates from Sorted List
Solved
Easy
Topics
Companies
Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode cur = head;
while(cur != null && cur.next != null){
if(cur.next.val == cur.val){
cur.next = cur.next.next;
}else{
cur = cur.next;
}
}
return head;
}
}160. Intersection of Two Linked Lists
Solved
Easy
Topics
Companies
Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode curA = headA;
ListNode curB = headB;
while(curA != curB){
if(curA != null){
curA = curA.next;
}else{
curA = headB;
}
if(curB != null){
curB = curB.next;
}else{
curB = headA;
}
}
return curA;
}
}