链表算法题

1、相交链表

解题思路：一起遍历两个链表，当pA遍历完之后就指向pB，pB遍历完之后就指向pA。这样pA、pB遍历的长度都是A+B+C，如果相遇就能返回交点，没相遇就返回空。

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode getIntersectionNode(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;}
}

2、反转链表

解题思路：用一个链表头p来存储遍历出来的节点，并且让每一个新结点的next是p。

/*** 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 p = null;ListNode h = head;while(h!=null){ListNode tmp = h.next;h.next = p;p = h;h = tmp;}return p;}
}

3、回文链表

解题思路：用快慢指针遍历整个链表，快指针遍历到结束的时候，慢指针就到了链表的中间位置，从中间位置开始反转链表，然后再比较前半部分和反转后的链表。（我最开始是选择将整个链表翻转，但是这样会导致原链表也翻转了，无法进行比较）

/*** 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 boolean isPalindrome(ListNode head) {if(head==null||head.next==null){return true;}ListNode slow = head;ListNode fast = head;while(fast!=null&&fast.next!=null){slow = slow.next;fast = fast.next.next;}ListNode p = null;while(slow!=null){ListNode tmp = slow.next;slow.next = p;p = slow;slow = tmp;}while(p!=null){if(p.val!=head.val){return false;}p = p.next;head = head.next;}return true;}
}

4、环形链表

解题思路：用快慢指针依次遍历，如果快指针等于慢指针，就说明有环，如果快指针的当前位置或者下一个位置是null，就说明没有环。

/*** Definition for singly-linked list.* class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public boolean hasCycle(ListNode head) {if(head==null||head.next==null){return false;}ListNode fast = head.next;ListNode slow = head;while(fast!=slow){if(fast==null||fast.next==null){return false;}fast = fast.next.next;slow = slow.next;}return true;}
}

5、环形链表II

解题思路：用快慢指针，当快指针和慢指针重合的时候，就说明有环，引入一个新的链表指向头指针，当他和慢指针同时移动，重合的地方就是环的入口。

/*** Definition for singly-linked list.* class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode detectCycle(ListNode head) {if(head==null||head.next==null){return null;}ListNode fast = head;ListNode slow = head;while(fast!=null){slow = slow.next;if(fast.next!=null){fast = fast.next.next;}else{return null;}if(fast == slow){ListNode p = head;while(p!=slow){p = p.next;slow = slow.next;}return p;}}return null;}
}

6、合并两个有序链表

解题思路：比较两个链表当前位置的值，将小的值添加到新链表中去，直到一个边表遍历完。将另一个链表没有遍历完的值添加到新链表中去。

/*** 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 mergeTwoLists(ListNode list1, ListNode list2) {if(list1==null){return list2;}if(list2==null){return list1;}ListNode h = new ListNode();ListNode p = h;while(list1!=null&&list2!=null){if(list1.val<list2.val){p.next = list1;list1 = list1.next;p = p.next;}else{p.next = list2;list2 = list2.next;p = p.next;}}while(list1!=null){p.next = list1;list1 = list1.next;p = p.next;}while(list2!=null){p.next = list2;list2 = list2.next;p = p.next;}return h.next;}
}

7、两两交换链表中的节点

解题思路：这道题需要弄一个虚拟头结点，这样能将所有的节点都按照同一种方式交换。

/*** 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 swapPairs(ListNode head) {if(head==null||head.next==null){return head;}ListNode h = new ListNode(0);h.next = head;ListNode p = h;while(head!=null&&head.next!=null){ListNode first = head;ListNode second = head.next;p.next = second;first.next = second.next;second.next = first;p = first;head = first.next;}return h.next;}
}

8、排序链表

题目描述：可以把链表存到数组，再排序，重新存到链表。

/*** 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 sortList(ListNode head) {if(head==null||head.next==null){return head;}ListNode p = head;int n =0;while(p!=null){p = p.next;n++;}int[] str = new int[n];p =head;for(int i = 0;i<n;i++){str[i] = p.val;p = p.next;}Arrays.sort(str);ListNode result = new ListNode(0);ListNode h = result;for(int i = 0;i<n;i++){result.next = new ListNode(str[i]);result = result.next;}return h.next;}
}