TC: O(N)
/** * 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) return null; ListNode current = head; ListNode pre = null; ListNode next = current.next; while(current!= null){ current.next = pre; pre = current; current = next; if(next!= null) next = next.next; } return pre; } } Or it can also done as (without using next pointer)
/** * 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 prev = null; ListNode current = head; while(head!=null){ head = head.next; current.next = prev; prev = current; current = head; } return prev; } } Delete a node in a linkedlist when the head of the node is not given in O(1)
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public void deleteNode(ListNode node) { node.val = node.next.val; node.next = node.next.next; } } Delete nth node from the back of the linkedlist
TC:O(N)
/** * 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) { // we will use fast and slow pointers for solving this problem //for avoiding edge case if there is only one node in the linkedList ListNode start = new ListNode(); start.next = head; // by this way we are ensuring that length of the list is atleast 2 ListNode fast = start; ListNode slow = start; for(int i =1;i<=n;++i){ fast =fast.next; } while(fast.next!=null){ fast = fast.next; slow = slow.next; } slow.next = slow.next.next; return start.next; } } Merge to sorted list
TC: O(n) ,where n is min(len(list1),len(list2))
/** * 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 l1, ListNode l2) { ListNode temp = new ListNode(0); ListNode current = temp; while(l1!=null && l2 != null){ if(l1.val < l2.val){ current.next = l1; current = l1; l1 = l1.next; } else { current.next = l2; current = l2; l2 = l2.next; } } if(l1==null) current.next = l2; else current.next = l1; return temp.next; } } 
Top comments (0)