面试过程中，总是被拷打，信心都要没了。但是也慢慢摸索出一些思路，希望对大家有帮助。
（需要多用一下ACM模式，力扣模式提供好了模板，自己在IDEA里面写的话，还是会有些陌生）
0、基本Java类型
1、用双指针思路去解决链表问题
定义一个单链表
class ListNode{
int val;
ListNode next;
ListNode(int x){
val = x;
next = null;
}
}
力扣21 - 合并两个有序链表
/**
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) {
//虚拟头结点
ListNode dummy = new ListNode(-1), p = dummy;
ListNode p1 = list1 ,p2 = list2;
while(p1 != null && p2 != null){
//比较p1和p2两个指针，把值较小的节点接到p指针
if( p1.val > p2.val){
p.next = p2;
p2 = p2.next;
}else{
p.next = p1;
p1 = p1.next;
}
p = p.next;
}
if(p1 != null){
p.next = p1;
}
if(p2 != null){
p.next = p2;
}
return dummy.next;
}
}
力扣19 - 删除倒数第k个节点
/**
* 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 removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode x = findFromEnd(dummy, n+1);
x.next = x.next.next;
return dummy.next;
}
private ListNode findFromEnd(ListNode head, int k) {
ListNode p1 = head;
for (int i = 0; i< k; i++){
p1 = p1.next;
}
ListNode p2 = head;
while( p1 != null){
p2 = p2.next;
p1 = p1.next;
}
return p2;
}
}
力扣876 - 链表的中间结点
/**
* 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 middleNode(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}
未完待续。。。。
