反转链表、
public class reverseList {
// 1->2->3->o 、 o<-1<-2<-3public ListNode reverseList(ListNode head){//反转链表ListNode prev=null;ListNode curr=head;while(curr!=null){ListNode next=curr.next;curr.next=prev;prev=curr;curr=next;}return prev;}public static void main(String[] args) {ListNode head = new ListNode(1);head.next = new ListNode(2);head.next.next = new ListNode(3);head.next.next.next = new ListNode(4);head.next.next.next.next = new ListNode(5);reverseList solution = new reverseList();ListNode re = solution.reverseList(head);while (re != null) {System.out.print(re.val + "");re = re.next;}}
}
相交链表、
import java.util.HashSet;
import java.util.Set;
public class interlinkedlist {public ListNode getIntersectionNode1(ListNode headA,ListNode headB){Set<ListNode>set=new HashSet<>();while(headA!=null){set.add(headA.next);headA=headA.next;}while(headB!=null){if(set.contains(headB)){return headB;}headB=headB.next;}return null;}public ListNode getIntersectionNode2(ListNode headA,ListNode headB){if(headA==null||headB==null) return null;ListNode pA=headA,pB=headB;while(pA!=pB){pA=pA==null?headB:pA.next;pB=pB==null?headA:pB.next;}return pA;}// 测试代码public static void main(String[] args) {// 创建两个链表// 链表 A: 4 -> 1 -> 8 -> 4 -> 5// 链表 B: 5 -> 6 -> 1 -> 8 -> 4 -> 5ListNode headA = new ListNode(4);headA.next = new ListNode(1);headA.next.next = new ListNode(8);headA.next.next.next = new ListNode(4);headA.next.next.next.next = new ListNode(5);ListNode headB = new ListNode(5);headB.next = new ListNode(6);headB.next.next = new ListNode(1);headB.next.next.next = headA.next.next; // 相交节点 8headB.next.next.next.next =headA.next.next.next;headB.next.next.next.next.next =headA.next.next.next.next;interlinkedlist solution = new interlinkedlist();ListNode intersection = solution.getIntersectionNode1(headA, headB);if (intersection != null) {System.out.println("Intersected at '" + intersection.val + "'");} else {System.out.println("No intersection");}}
}
class ListNode {int val;ListNode next;public ListNode() {}public ListNode(int val, ListNode next) {this.val = val;this.next = next;}ListNode(int x) {this.val = x;this.next = null;}
}
回文链表、
//核心思想是通过递归的方式从链表的尾部向前进行比较，同时用一个前指针从头部向尾部进行比较
package org.example;
public class PalindromeLinkedList {private ListNode frontPointer;private boolean recursivelyCheck(ListNode currentNode) {if (currentNode != null) {if (!recursivelyCheck(currentNode.next)) {return false;}if (currentNode.val != frontPointer.val) {return false;}frontPointer = frontPointer.next;}return true;}public boolean isPalindrome(ListNode head) {frontPointer = head;return recursivelyCheck(head);}public static void main(String[] args) {// 创建链表 1 -> 2 -> 2 -> 1ListNode node1 = new ListNode(1);ListNode node2 = new ListNode(2);ListNode node3 = new ListNode(2);ListNode node4 = new ListNode(3);node1.next = node2;node2.next = node3;node3.next = node4;PalindromeLinkedList solution = new PalindromeLinkedList();boolean result = solution.isPalindrome(node1);System.out.println("链表是否是回文: " + result);}
}
