阅读量:0
链表反转
给定单链表的头节点 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=null if(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; }