1. Find the length of the list
public int getLength(ListNode head){
int length = 0;
ListNode tmpNode = head;
while(tmpNode! =null){
length++;
tmpNode = tmpNode.next;
}
return length;
}
Copy the code2. List flipping (traversal recursive method)
/ * * * * preNode traversing curNode left left left nextNode * * null -- -- -- -- -- - > 2-1 -- -- -- -- -- -- -- -- -- -- - > > 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 the rollover
preNode = curNode; / / preNode backwards
curNode = nextNode; / / curNode backwards
}
return preNode;
}
/ / the 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 backdirection
head.next = null; // Remove the old pointer
return last;
}
Copy the code3. Find the reciprocal KTH node
/** * use two Pointers first and second to traverse the list head, and first is k nodes ahead of second. When first traverses the end of list *, second is exactly the KTH to last node */
public ListNode getKthFromEnd(ListNode head, int k) {
if(head == null) return head; / / sentence
ListNode first = head;
ListNode second = head;
ListNode cur = head;
for (int i = 0; i < k ; i++) { //first traverses k nodes first
first = first.next;
}
while(first ! =null) {//first is null after the last node
first = first.next;
second = second.next;
}
return second;
}
Copy the code4. Find the intermediate node of the linked list
// If the length of the list is even, return the first 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 the code5. Linked list division
// Given a single linked list and the value x, partition the list such that all nodes less than x are ranked 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;
returnleftDummy.next; }}Copy the code6. Fast sorting to achieve single-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);
returnnode; }}Copy the code7. Merge to achieve single-linked list sort
public ListNode sortList(ListNode head) {
// 1
if (head == null || head.next == null) {
return head;
}
// 2, find the middle node of the list and break the list & recursion down
ListNode midNode = middleNode(head);
ListNode rightHead = midNode.next;
midNode.next = null;
ListNode left = sortList(head);
ListNode right = sortList(rightHead);
// 3. Current layer business operation (merge ordered linked list)
return mergeTwoLists(left, right);
}
// Find the middle node of the list (876.
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 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 the code8. Merge two ordered single-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;
}
// At most one of l1 and L2 has not been merged, we can directly point to the end of the unmerged list
tempNode.next = l1 == null ? l2 : l1;
return node.next;
}
Copy the code9. Complex list replication
// Reference to Offer 35. Copy complex linked lists
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 the original node -> New node Map
while(cur ! =null) {
map.put(cur, new Node(cur.val));
cur = cur.next;
}
cur = head;
// 4. Build next and random Pointers to the new list
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 first node of the new list
return map.get(head);
}
Copy the code10. Determine if the list has rings
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 the code11. Find the first node of the ring 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 the code12. Determine whether two acyclic singly linked lists intersect
- The most direct method is to determine whether each node of A list is in B list, but the time complexity of this method is O(Length(A) * Length(B)).
- Method two translates into a ring problem. Appending B to A, if the resulting list has A ring, the two lists intersect. You can use the fast and slow Pointers discussed earlier to determine whether there is a ring, but there is an easier way. If the linked list B intersects with the linked list A, all the nodes of the linked list B are in the ring when the linked list B is connected behind the linked list A. Therefore, we only need to traverse the linked list B to see whether it will return to the starting point to determine whether it intersects. This method requires traversing A linked list first to find the tail node, and then traversing B linked list once to determine whether A ring is formed. The time complexity is O(Length(A) + Length(B)).
- Method three, in addition to the problem of ring transformation, 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 way to do it is to go through the A list, remember the tail nodes, and then go through the B list, compare the tail nodes of the two lists, and if they are the same, they will intersect, if they are different, they will not intersect. The time complexity is O(Length(A) + Length(B)), the space complexity is O(1), the idea is simpler than solution 2.
// Method 3 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 the code13. Find the first intersection of two acyclic lists
- Method one: If two lists have a common node, then they are the same from the common node to the end of the list, so we just need to start at the end of the list, search forward, and find the last node that is the same. But the one-way list given by the problem, we can only search backwards, in this case, we can use the stack to complete. First, put the two linked lists into two stacks in turn, and then compare whether the top nodes of the two stacks are the same. If they are the same, they will be removed from the stack. If they are different, then the last same node is the return value we want.
- The second method is to find the length of the two lists, and then let the length of the two lists go first, and then go together until the first common node is found.
- Method 3 Since both lists have no rings, we can join the second list after the first list, thus transforming the problem into the entry node problem of the ring.
- Methods four two Pointers p1 and p2 respectively to list A and list B, they walk forward at the same time, when go to the end node, move on to another list, such as p1 to list A tail node, the next step is to list B, p2 to list B end node, the next step is to list A, when p1 = = p2, is the intersection point 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) {// Start from another list after traversing the list
// When p1 and p2 are switched to another list, they are aligned:
// (1) If the list intersects, p1 == p2 is the first intersecting point
// if the list does not intersect, p1 and p2 move to the end at the same time, p1 = p2 = null, and exit the loop
p1 = (null == p1) ? headB : p1.next;
p2 = (null == p2) ? headA : p2.next;
}
return p1;
}
Copy the code