【实战】算法思路总结

面试过程中，总是被拷打，信心都要没了。但是也慢慢摸索出一些思路，希望对大家有帮助。

（需要多用一下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;

}

}