Linked list algorithm problem

Linked list algorithm problem

1. Find the length of the linked list

public int getLength (ListNode head) { int length = 0 ; ListNode tmpNode = head; while (tmpNode!= null ){ length++; tmpNode = tmpNode.next; } return length; } Copy code

2. Linked list flip (traversal method recursive method)

/** * Traversal method * preNode curNode nextNode * * null 1 ------> 2 ------> 3 ------> 4 */ public ListNode reverseLinkedList (ListNode head) { ListNode preNode = null ; ListNode curNode = head; ListNode nextNode = null ; while (curNode != null ){ nextNode = curNode.next; curNode.next = preNode; //curNode points to flip preNode = curNode; //preNode moves backward curNode = nextNode; //curNode moves backward } return preNode; } //Recursive method public ListNode reverseLinkedList (ListNode head) { if (head.next == null ) return head; ListNode last = reverseList(head.next); head.next.next = head; //Create a new reverse point head.next = null ; //Remove the old point return last; } Copy code

3. Find the Kth node from the bottom

/** * Use two pointers first and second to traverse from the linked list head, and first is ahead of second by k nodes. When first traverses to the linked list * After the end node, second is exactly the kth node from the bottom */ public ListNode getKthFromEnd (ListNode head, int k) { if (head == null ) return head; //Special judgment ListNode first = head; ListNode second = head; ListNode cur = head; for ( int i = 0 ; i <k; i++) { //first node first traverse k nodes first = first.next; } while (first != null ){ //first traverse to null after the tail node first = first.next; second = second.next; } return second; } Copy code

4. Find the middle node of the linked list

//If the length of the linked list is an even number, return the first node of the middle two nodes public ListNode middleNode (ListNode head) { ListNode fast = head; ListNode slow = head; while (fast.next != null && fast.next.next != null ){ fast = fast.next.next; slow = slow.next; } return slow; } Copy code

5. Linked list division

//Title description: Given a singly linked list and the value x, divide the linked list so that all nodes less than x are arranged before nodes greater than or equal to x. //Input: 1-->3-->0-->7-->2-->null x = 3 //Output: 1-->0-->2-->3-->7- ->null public class Solution { public ListNode partition (ListNode head, int x) { if (head == null ) return null ; ListNode leftDummy = new ListNode( 0 ); ListNode rightDummy = new ListNode( 0 ); ListNode left = leftDummy, right = rightDummy; while (head != null ) { if (head.val < x) { left.next = head; left = head; } else { right.next = head; right = head; } head = head.next; } right.next = null ; left.next = rightDummy.next; return leftDummy.next; } } Copy code

6. Fast sorting realizes singly linked list sorting

class Solution { public ListNode sortList (ListNode head) { return quickSort(head, null ); } public ListNode quickSort (ListNode head, ListNode end) { if (head == end || head.next == end) return head; ListNode left = head, right = head, p = head.next; while (p != end){ ListNode next = p.next; if (p.val <head.val){ p.next = left; left = p; } else { right.next = p; right = p; } p = next; } right.next = end; ListNode node = quickSort(left,head); head.next = quickSort(head.next,end); return node; } } Copy code

7. Merge to realize singly linked list sorting

public ListNode sortList (ListNode head) { //1. Recursive end condition if (head == null || head.next == null ) { return head; } //2. Find the intermediate node of the linked list and disconnect the linked list & descend recursively ListNode midNode = middleNode(head); ListNode rightHead = midNode.next; midNode.next = null ; ListNode left = sortList(head); ListNode right = sortList(rightHead); //3. Current layer business operations (merging ordered linked lists) return mergeTwoLists(left, right); } //Find the middle node of the linked list (876. The middle node of the linked list) private ListNode middleNode (ListNode head) { if (head == null || head.next == null ) { return head; } ListNode slow = head; ListNode fast = head.next.next; while (fast != null && fast.next != null ) { slow = slow.next; fast = fast.next.next; } return slow; } //Merge two ordered linked lists (21. Merge two ordered linked lists) private ListNode mergeTwoLists (ListNode l1, ListNode l2) { ListNode sentry = new ListNode(- 1 ); ListNode curr = sentry; while (l1 != null && l2 != null ) { if (l1.val <l2.val) { curr.next = l1; l1 = l1.next; } else { curr.next = l2; l2 = l2.next; } curr = curr.next; } curr.next = l1 != null ? l1: l2; return sentry.next; } Copy code

8. Merge two ordered singly linked lists

public ListNode mergeLinkedList (ListNode l1,ListNode l2) { ListNode node = new ListNode(); ListNode tempNode = node; while(l1 !=null && l2 !=null){ if(l1.val <= l2.val){ tempNode.next=l1; l1 = l1.next; }else{ tempNode.next =l2; l2 = l2.next; } tempNode = tempNode.next; } // l1 l2 tempNode.next = l1 == null ? l2 : l1; return node.next; }

9.

//Sword refers to Offer 35. Copy of complex linked list public Node copyRandomList(Node head) { if(head == null) return null; Node cur = head; Map<Node, Node> map = new HashMap<>(); //3. Copy each node and create a Map mapping of "original node -> new node" while (cur != null ) { map.put(cur, new Node(cur.val)); cur = cur.next; } cur = head; //4. The next and random of the new linked list point to while (cur != null ) { map.get(cur).next = map.get(cur.next); map.get(cur).random = map.get(cur.random); cur = cur.next; } //5. Return the head node of the new linked list return map.get(head); } Copy code

10. Determine whether the linked list has a ring

public boolean hasCycle (ListNode head) { if (head == null || head.next == null ) return false ; ListNode fast = head ,slow = head; while ( true ){ if (fast == null || fast.next == null ) return false ; fast = fast.next.next; slow = slow.next; if (fast == slow) return true ; } } Copy code

11. Find the first node of the circular linked list into the ring

public ListNode detectCycle (ListNode head) { ListNode fast = head, slow = head; while ( true ) { if (fast == null || fast.next == null ) return null ; fast = fast.next.next; slow = slow.next; if (fast == slow) break ; } fast = head; while (slow != fast) { slow = slow.next; fast = fast.next; } return fast; } Copy code

12. Determine whether two acyclic singly linked lists intersect

  • Method One The most direct method is to determine whether each node of the A linked list is in the B linked list, but the time complexity of this method is O(Length(A) * Length(B)).
  • Method two is transformed into a ring problem. Connect the B linked list to the A linked list. If the resulting linked list has a ring, it means that the two linked lists intersect. You can judge whether there is a loop using the fast and slow pointers discussed earlier, but there is a simpler way. If the B-linked list and the A-linked list intersect, when the B-linked list is connected to the A-linked list, all the nodes of the B-linked list are in the ring, so at this time, you only need to traverse the B-linked list to see if it will return to the starting point to determine whether it intersects. This method needs to traverse the A linked list once to find the tail node, and then traverse the B linked list once to determine whether a ring is formed. The time complexity is O(Length(A) + Length(B)).
  • Method 3 In addition to the problem of turning into a ring, you can also use the feature of " if two linked lists intersect at a node, then the following nodes are common ", if two linked lists intersect, then the last node must be common. So another solution can be drawn. First traverse the A linked list, remember the tail node, and then traverse the B linked list, compare the tail nodes of the two linked lists, if they are the same, they will intersect, and if they are different, they will not. The time complexity is O(Length(A) + Length(B)), the space complexity is O(1), and the idea is simpler than solution 2.
//Method three code public boolean isIntersect (ListNode headA, ListNode headB) { if ( null == headA || null == headB) { return false ; } if (headA == headB) { return true ; } while ( null != headA.next) { headA = headA.next; } while ( null != headB.next) { headB = headB.next; } return headA == headB; } Copy code

13. Find the first intersection point of two acyclic singly linked lists

  • Method 1: If two linked lists have a common node, they are the same from the common node to the end of the linked list. Therefore, we only need to start from the end of the linked list and search forward to find the last identical node. can. But for the singly linked list given by the title, we can only search from front to back. At this time, we can use the stack to complete it. First install the two linked lists into the two stacks in turn, and then compare whether the top nodes of the two stacks are the same, if they are the same, pop the stack, if they are different, the last same node is the return value we want.
  • Method 2 First find out the length of the two linked lists, and then let the long one walk the difference between the lengths of the two linked lists first, and then walk together until the first common node is found.
  • Method 3 Since the two linked lists have no loops, we can connect the second linked list to the back of the first linked list, thus turning the problem into an entry node problem for finding a ring.
  • Method 4 The two pointers p1 and p2 point to the linked list A and the linked list B respectively. They move forward at the same time. When they reach the end node, they turn to another linked list. For example, when p1 reaches the end node of the linked list A, the next step is to go to When the linked list B and p2 reach the end node of the linked list B, the next step is to the linked list A, when p1==p2, it is the intersection point of the linked list
public ListNode getIntersectionNode (ListNode headA, ListNode headB) { if ( null == headA || null == headB) { return null ; } if (headA == headB) { return headA; } ListNode p1 = headA; ListNode p2 = headB; while (p1 != p2) { //After traversing the linked list, start from another linked list //When both p1 and p2 are changed to another linked list, they are aligned: //(1) If the linked lists intersect, p1 = = p2 is the first intersection point //(2) If the linked list does not intersect, p1 and p2 move to the end at the same time, p1 = p2 = null, and then exit the loop p1 = ( null == p1)? headB: p1.next ; p2 = ( null == p2)? headA: p2.next; } return p1; } Copy code