面試過程中，總是被拷打，信心都要沒了。但是也慢慢摸索出一些思路，希望對大家有幫助。
（需要多用一下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;
? ? }
}
未完待續。。。。
