/** *!!! dummy head is always very handy , try to use it as much as possible * 添加虚节点方式 * 时间复杂度 O(n) * 空间复杂度 O(1) * @param head * @param val * @return */ public ListNode removeElements(ListNode head, int val) { if (head == null) { return head; } // 因为删除可能涉及到头节点，所以设置dummy节点，统一操作 ListNodedummy=newListNode(-1, head); ListNodepre= dummy; ListNodecur= head; while (cur != null) { if(cur.val == val){ pre.next = cur.next; cur = cur.next; }else{ pre = pre.next; cur = cur.next; } } return dummy.next; //!!!! notice, here you want to return dummy.next not head } /** * 不添加虚拟节点方式 * 时间复杂度 O(n) * 空间复杂度 O(1) * @param head * @param val * @return */ public ListNode removeElements(ListNode head, int val) { while (head != null && head.val == val) { head = head.next; } // 已经为null，提前退出 if (head == null) { return head; } // 已确定当前head.val != val ListNodepre= head; ListNodecur= head.next; while (cur != null) { if (cur.val == val) { pre.next = cur.next; } else { pre = cur; } cur = cur.next; } return head; } /** * 不添加虚拟节点and pre Node方式 * 时间复杂度 O(n) * 空间复杂度 O(1) * @param head * @param val * @return */
//MY WAY: //this step is to delete all the val that is in the beginning og the list while(head != null && head.val == val) /* this step is necessary because when you go through the list current list can only delete its next list, can't delete itself. */ head = head.next; ListNodecurr= head; while(curr != null && curr.next != null){ if(curr.next.val == val ) curr.next = curr.next.next; else{ curr = curr.next; } } return head; //my way 2: classSolution { public ListNode removeElements(ListNode head, int val) { ListNodedumb=newListNode(0, head); ListNodepointer= dumb; //if(head == null) return head; while(pointer.next != null){ if(pointer.next.val == val){ pointer.next = pointer.next.next; }else{ pointer = pointer.next; // 注意这句话在else里面 } } return dumb.next; // here is dumb.next not head } }
/** * Your MyLinkedList object will be instantiated and called as such: * MyLinkedList obj = new MyLinkedList(); * int param_1 = obj.get(index); * obj.addAtHead(val); * obj.addAtTail(val); * obj.addAtIndex(index,val); * obj.deleteAtIndex(index); */
/** * 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; } * } */ classSolution { public ListNode reverseList(ListNode head) { ListNodepre=null; ListNodetemp=null; ListNodecur= head; while(cur != null){ temp = cur.next; //notice: here need a temp to keep track of cur.next cur.next = pre; pre = cur; cur = temp; } return pre; //return pre not cur, cause cur is the null linkedNote after the whole linkedList } }
// WRONG!!! Draw a graph then you will see why this method is stupidly wrong. // Here we have to use a dummy head. classSolution { public ListNode swapPairs(ListNode head) { ListNodefirstnode= head; ListNode temp; ListNode secondnode; while (firstnode != null && firstnode.next != null && firstnode.next.next != null) { temp = firstnode.next.next; secondnode = firstnode.next; secondnode.next = firstnode; firstnode.next = temp.next; firstnode = temp; } return head;
} }
// Below is the right solution (= // if you use dummy head then you don't need to cosider the special situations like the start of the link and the end of the link. It makes coding more simple classSolution { public ListNode swapPairs(ListNode head) { if(head == null || head.next == null) return head; ListNodedummy=newListNode(-1, head); ListNodecur= dummy; ListNode first ; ListNode second ; ListNode temp; while(cur.next != null && cur.next.next != null){ first = cur.next; // second = first.next; // temp =second.next; // i feel like those three lines need attention, do this at the beginning of the iteration! //我觉得这个申明放在while的最前面而不是后面是因为它可以检查最开始进入循环的时候cur是不是空的情况 second.next = first; first.next = temp; cur.next = second;
cur = first; } return dummy.next; } }
second try, even it’s right, but you need to consider a lot of situations which makes the coding complicated.这个方法每次循环横跨了四个linkedlist.
therefore, the first approach is way better
so when you do the loop, you dont want the 循环跨度太大，不然你得考虑很多特殊情况。
class Solution { public ListNode swapPairs(ListNode head) { // Check if the list is empty or has only one element if (head == null || head.next == null) { return head; }
// Initialize the result as the second node ListNode res = head.next;
// Initialize pointers for swapping ListNode first = head; ListNode second = head.next; ListNode third = head.next.next;
// Swap pairs while traversing the list while (true) { // Swap the first and second nodes second.next = first;
// Check if there's a third node if (third != null) { // Check if there's a fourth node if (third.next != null) { first.next = third.next; } else { first.next = third; } } else { first.next = null; }
// If there are no more nodes to swap, return the result if (first.next == null) { return res; }
// Update pointers for the next pair of nodes first = third; second = first.next;
// Check if there's a third node for the next pair if (second.next != null) { third = second.next; } else { third = null; } } } }
classSolution { public ListNode removeNthFromEnd(ListNode head, int n) { ListNodedummy=newListNode(0); dummy.next = head; ListNodecount= dummy; intm=0; // caculate the length of the list while(count.next != null){ count = count.next; m++; } if(m == 1){ //the lostnode only has one element head = null; return head; } // get to the note which is right before the one that is going to be deleted ListNodedelete= dummy; for( inti=0 ; i < m - n ; i ++){ delete = delete.next; } //delete the last element if( n == 1 ){ delete.next = null; } // delete the first element elseif( n == m){ return head.next; } //delete the element in between else { delete.next = delete.next.next; } return head; } }
Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3 Output: Intersected at '8' Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,6,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B. - Note that the intersected node's value is not 1 because the nodes with value 1 in A and B (2nd node in A and 3rd node in B) are different node references. In other words, they point to two different locations in memory, while the nodes with value 8 in A and B (3rd node in A and 4th node in B) point to the same location in memory.
publicclassSolution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { // length of A ListNodecurA=newListNode(); curA.next = headA; intlenA=0; while( curA.next != null){ curA = curA.next; lenA++; } // length of B ListNodecurB=newListNode(); curB.next = headB; intlenB=0; while( curB.next != null){ curB = curB.next; lenB++; } // swap A and B if a.len < b.len if(lenA < lenB){ int temp; temp = lenA; lenA = lenB; lenB = temp; curA = headB; curB = headA; }else{ curA = headA; curB = headB; } // length gap intgap= lenA - lenB; // make cur A and B at the same place of the list while(gap != 0){ curA = curA.next; gap--; } // find the same element while(curA != null){ if(curA == curB){ // it's curA == curB NOT curA.val == curB.val return curA; } curA = curA.next; curB = curB.next; } returnnull; //！！！！！！！！！！！！！！ not new ListNode(null); } }
Input: head = [3,2,0,-4], pos = 1 Output: tail connects to node index 1 Explanation: There is a cycle in the linked list, where tail connects to the second node.
/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ publicclassSolution { public ListNode detectCycle(ListNode head) { ListNodefast= head; ListNodeslow= head; // here need to check if fast and fast.next is null, can't check if fast == slow directly cause there are cases without loops so fast can never equal to slow while(fast != null && fast.next != null){ // find where fast and slow meet fast = fast.next.next; slow = slow.next; if(fast == slow){ // there's a cycle ListNodenode1= head; ListNodenode2= fast; while(node1 != node2 ){ // 两个指针，从头结点和相遇结点，各走一步，直到相遇，相遇点即为环入口(x = z) node1 = node1.next; node2 = node2.next; } return node1; } } returnnull; } }
Given the head of a singly linked list where elements are sorted in ascending order, convert it to a
*height-balanced*
binary search tree.
Example 1:
1 2 3
Input: head = [-10,-3,0,5,9] Output: [0,-3,9,-10,null,5] Explanation: One possible answer is [0,-3,9,-10,null,5], which represents the shown height balanced BST.
