链表反转
给定单链表的头节点 head ，请反转链表，并返回反转后的链表的头节点。
解题思路
cur遍历指向当前节点，pre指向cur前一个节点，链表反转就是将cur指向自己的前一个节点 pre，然后 pre=cur cur=tmp 向后移动 终止条件是cur当前节点不为空
代码如下：
/*** 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 cur = head, pre = null;//cur遍历指向当前节点，pre指向cur前一个节点，链表反转就是将cur指向自己的前一个节点 pre，然后 pre=cur cur=tmp 向后移动 终止条件是cur当前节点不为空while(cur != null) {ListNode nxt = cur.next; // 存cur下一个节点节点cur.next = pre; // cur的下一个节点改为指向前面的节点pre = cur; // pre 指向 cur 后移过程cur = nxt; // cur 访问下一节点 后移过程}return pre;}
}
相交链表
给定两个单链表的头节点 headA 和 headB ，请找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
解题思路：
1、哈希表判断法
遍历其中一个链表，将其放在hashset集中，然后再判断另一个链表的各个节点是否在hashset集中，如果另一个链表的某个节点出现在hashset集中，那么此节点之后的节点必然出现在hashset集中，当前节点即为两链表的相交节点，如果两链表不相交，hashset集里面可以将全部节点放下，此时返回null
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {HashSet<ListNode> listNodes = new HashSet<>();ListNode temp = headA;while (temp!=null){listNodes.add(temp);temp=temp.next;}temp=headB;while (temp!=null){if (listNodes.contains(temp))return temp;temp=temp.next;}return null;}2、双指针法（时间复杂度更低）
任意一个链表为空则必不相交，判断是否为空；相交的链表如果遍历的话走过的长度一致，故一定在相交节点处第一次相遇
public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {ListNode A =headA;ListNode B=headB;while(A!=B){//A==B有两种情况，AB链表相交 A=B=nullif(A==null) A=headB;else A=A.next;if(B==null) B=headA;else B=B.next;}return A;}回文链表
解题代码：
/*** 复制链表值到数组列表中。* 使用双指针法判断是否为回文。* @param head* @return*/public boolean isPalindrome(ListNode head) {ArrayList<Integer> values = new ArrayList<>();ListNode temp =head;while (temp!=null){values.add(temp.val);temp=temp.next;}int front =0;int back =values.size()-1;while (front<back){if (values.get(front)!=values.get(back)){return false;}front++;back--;}return true;}链表成环的判断
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
解题思路
用快慢指针，如果成环一定会相遇
public boolean hasCycle(ListNode head) {if(head==null||head.next==null){return false;}ListNode fast=new ListNode(-1);ListNode slow=new ListNode(-1);fast=head.next;slow=head;while(fast!=slow){if(fast==null||fast.next==null){return false;}fast=fast.next.next;slow=slow.next;}return true;}链表成环位置判断
给定一个链表，返回链表开始入环的第一个节点。 从链表的头节点开始沿着 next 指针进入环的第一个节点为环的入口节点。如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。
解题思路：
1、哈希表判断
public ListNode detectCycle(ListNode head) {ListNode pos = head;Set<ListNode> visited = new HashSet<ListNode>();while (pos != null) {if (visited.contains(pos)) {//如果哈希表里第一次有，就成环return pos;} else {//如果哈希表里没有就添加visited.add(pos);}pos = pos.next;}return null;}2、快慢指针，判断是否成环，如果成环了，让快指针指向head，之后两指针保持相同速度遍历，第一次相遇的点就是环连接点。
（可简记一个推导结论：从相遇点到入环点的距离加上 n−1 圈的环长，恰好等于从链表头部到入环点的距离。）
public ListNode detectCycle(ListNode head) {ListNode fast = head;ListNode slow = head;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;if (slow == fast) {// 有环fast = head;while (fast != slow) {fast = fast.next;slow = slow.next;}return fast;}}// 无环return null;}有序链表合并
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
解题代码：
/**思路：如果l1和l2都不为空的话，首先定义一个新的节点，值设为-1 便于之后返回新的链表合并链表时如果一个链表先为空，则将另一个链表的剩余部分直接加到新链表后面*/public ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode newhead =new ListNode(-1);ListNode listNode=newhead;while (list1!=null&&list2!=null){if (list1.val<=list2.val){listNode.next=list1;list1=list1.next;}else {listNode.next=list2;list2=list2.next;}listNode=listNode.next;}listNode.next=list1==null?list2:list1;return newhead.next;}
)
