1.選擇排序?qū)⒁雅判虿糠侄x在左端，然后選擇未排序部分的最小元素和未排序部分的第一個(gè)元素交換。
2.冒泡排序?qū)⒁雅判虿糠侄x在右端，在遍歷未排序部分的過(guò)程執(zhí)行交換，將最大元素交換到最右端。
3.插入排序?qū)⒁雅判虿糠侄x在左端，將未排序部分元的第一個(gè)元素插入到已排序部分合適的位置。
一. 冒泡排序
- 從頭開(kāi)始比較每一對(duì)相鄰元素，如果第1個(gè)比第2個(gè)大，就交換它們的位置
? 執(zhí)行完一輪后，最末尾那個(gè)元素就是最大的元素 - 忽略 1 中曾經(jīng)找到的最大元素，重復(fù)執(zhí)行步驟 1，直到全部元素有序
public static void bubbleSort(int[] array){
for ( int i = 0; i< array.length-1; i++ ){
for ( int j = 0; j < array.length-1-i; j++ ) {
if ( array[j] > array[j+1] ){
int tem = array[j];
array[j] = array[j+1];
array[j+1] = tem;
}
}
}
}
static void bubbleSort(Integer[] array) {
for (int end = array.length - 1; end > 0; end--) {
for (int begin = 1; begin <= end; begin++) {
if (array[begin] < array[begin - 1]) {
int tmp = array[begin];
array[begin] = array[begin - 1];
array[begin - 1] = tmp;
}
}
}
}
優(yōu)化一: 如果序列已經(jīng)完全有序，可以提前終止冒泡排序
static void bubbleSort2(Integer[] array) {
for (int end = array.length - 1; end > 0; end--) {
boolean sorted = true;
for (int begin = 1; begin <= end; begin++) {
if (array[begin] < array[begin - 1]) {
int tmp = array[begin];
array[begin] = array[begin - 1];
array[begin - 1] = tmp;
sorted = false;
}
}
if (sorted) break;
}
}
優(yōu)化二: 如果序列尾部已經(jīng)局部有序，可以記錄最后1次交換的位置，減少比較次數(shù)
static void bubbleSort3(Integer[] array) {
for (int end = array.length - 1; end > 0; end--) {
// sortedIndex的初始值在數(shù)組完全有序的時(shí)候有用
int sortedIndex = 1;
for (int begin = 1; begin <= end; begin++) {
if (array[begin] < array[begin - 1]) {
int tmp = array[begin];
array[begin] = array[begin - 1];
array[begin - 1] = tmp;
sortedIndex = begin;
}
}
end = sortedIndex;
}
}
二. 選擇排序
首先在未排序序列中找到最小元素，存放到排序序列的起始位置;
然后，再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最小元素，然后放到已排序序列的末尾。
以此類(lèi)推，直到所有元素均排序完畢。
public static void selectSort(int[] array){
for ( int i = 0; i<array.length; i++ ){
int minIndex = I;
for ( int j = i; j < array.length; j++ ) {
if( array[minIndex] > array[j] ) {
minIndex = j; // 將最小數(shù)的索引保存
}
}
int tem = array[minIndex];
array[minIndex] = array[I];
array[i] = tem;
}
}
三. 插入排序
public static void insertSort(int[] array){
for ( int i= 1; i<array.length; i++){
for(int j= i; j>0 && array[j-1] > array[j] ; j--){
int tem = array[j-1];
array[j-1] = array[j];
array[j] = tem;
}
}
}
優(yōu)化:將【交換】轉(zhuǎn)為【挪動(dòng)】
① 先將待插入的元素備份
② 頭部有序數(shù)據(jù)中比待插入元素大的，都朝尾部方向挪動(dòng)1個(gè)位置
③ 將待插入元素放到最終的合適位置
public static void insertSort2(int[] array){
for (int i = 1; i < array.length; i++) {
int e = array[i];// 尋找元素e的插入合適位置;
int j;
for(j = i; j>0 && array[j-1] > e; j--){
array[j] = array[j-1];
}
array[j] = e;
}
}
因?yàn)椴迦肱判蚩梢蕴崆敖Y(jié)束循環(huán),所以當(dāng)數(shù)據(jù)中逆序?qū)Φ臄?shù)量極少時(shí)，插入排序的效率特別高;甚至速度比 O (nlogn) 級(jí)別的快速排序還要快;
// 對(duì)arr[l...r]的區(qū)間使用InsertionSort排序
public static void sort(Comparable[] arr, int l, int r){
for( int i = l + 1 ; i <= r ; i ++ ){
Comparable e = arr[i];
int j = I;
for( ; j > l && arr[j-1].compareTo(e) > 0 ; j--)
arr[j] = arr[j-1];
arr[j] = e;
}
}
四. 歸并排序
① 不斷地將當(dāng)前序列平均分割成2個(gè)子序列
? 直到不能再分割（序列中只剩1個(gè)元素）
② 不斷地將2個(gè)子序列合并成一個(gè)有序序列
? 直到最終只剩下1個(gè)有序序列
public static void mergeSort(int[] array) {
_sort(array, 0, array.length - 1);
}
//遞歸使用歸并排序,對(duì)arr[l...r]的范圍進(jìn)行排序
public static void _sort(int[] array, int l, int r) {
if (l >= r) return;
int mid = (r - l) / 2 + l;// (r+l)/2
_sort(array, l, mid);
_sort(array, mid + 1, r);
_merge(array, l, mid, r);
}
// 將arr[l...mid]和arr[mid+1...r]兩部分進(jìn)行歸并
public static void _merge(int[] arr, int l, int mid, int r) {
int[] aux = Arrays.copyOfRange(arr,l,r+1);
// 初始化，i指向左半部分的起始索引位置l；j指向右半部分起始索引位置mid+1
int i = l, j = mid+1;
for( int k = l ; k <= r; k ++ ){
if( i > mid ){ // 如果左半部分元素已經(jīng)全部處理完畢
arr[k] = aux[j-l]; j ++;
}
else if( j > r ){ // 如果右半部分元素已經(jīng)全部處理完畢
arr[k] = aux[i-l]; i ++;
}
else if( aux[i-l] < aux[j-l] ) { // 左半部分所指元素 < 右半部分所指元素
arr[k] = aux[i-l]; i ++;
}
else{ // 左半部分所指元素 >= 右半部分所指元素
arr[k] = aux[j-l]; j ++;
}
}
}
優(yōu)化：
// 遞歸使用歸并排序,對(duì)arr[l...r]的范圍進(jìn)行排序
private static void sort(int[] arr, int l, int r) {
// 優(yōu)化2: 對(duì)于小規(guī)模數(shù)組, 使用插入排序
if (r - l <= 15) {
InsertionSort.sort(arr, l, r);
return;
}
int mid = (l + r) / 2;
sort(arr, l, mid);
sort(arr, mid + 1, r);
// 優(yōu)化1: 對(duì)于arr[mid] <= arr[mid+1]的情況,不進(jìn)行merge
// 對(duì)于近乎有序的數(shù)組非常有效,但是對(duì)于一般情況,有一定的性能損失
if (arr[mid] > arr[mid + 1])
_merge(arr, l, mid, r);
}
Merge Sort是我們學(xué)習(xí)的第一個(gè)O(nlogn)復(fù)雜度的算法。它可以在1秒之內(nèi)輕松處理100萬(wàn)數(shù)量級(jí)的數(shù)據(jù)。 注意：不要輕易嘗試使用SelectionSort, InsertionSort或者BubbleSort處理100萬(wàn)級(jí)的數(shù)據(jù)，否則，你就見(jiàn)識(shí)了O(n^2)的算法和O(nlogn)算法的本質(zhì)差異：）
歸并排序是一種穩(wěn)定的排序方法。和選擇排序一樣，歸并排序的性能不受輸入數(shù)據(jù)的影響，但表現(xiàn)比選擇排序好的多，因?yàn)槭冀K都是O(nlogn）的時(shí)間復(fù)雜度。代價(jià)是需要額外的內(nèi)存空間。
五. 快速排序
① 從序列中選擇一個(gè)軸點(diǎn)元素（pivot）
? 假設(shè)每次選擇 0 位置的元素為軸點(diǎn)元素
② 利用 pivot 將序列分割成 2 個(gè)子序列
? 將小于 pivot 的元素放在pivot前面（左側(cè)）
? 將大于 pivot 的元素放在pivot后面（右側(cè)）
? 等于pivot的元素放哪邊都可以
③ 對(duì)子序列進(jìn)行 ① ② 操作
? 直到不能再分割（子序列中只剩下1個(gè)元素）
【注意】 在軸點(diǎn)左右元素?cái)?shù)量比較均勻的情況下，同時(shí)也是最好的情況，時(shí)間復(fù)雜度O(nlogn)。 如果軸點(diǎn)左右元素?cái)?shù)量極度不均勻，比如已經(jīng)排好序的數(shù)組，最壞的情況時(shí)間復(fù)雜度就會(huì)降到 O(n^2)。 為了降低最壞情況的出現(xiàn)概率，一般采取的做法是 隨機(jī)選擇軸點(diǎn)元素。
public static void sort(Integer[] arr) {
sort(arr, 0, arr.length - 1);
}
// 遞歸使用快速排序,對(duì)arr[l...r]的范圍進(jìn)行排序
private static void sort(Integer[] arr, int l, int r) {
// 對(duì)于小規(guī)模數(shù)組, 使用插入排序
if (r - l <= 15) {
InsertionSort.sort(arr, l, r);
return;
}
// if (l >= r) return;
int p = partition(arr, l, r);
sort(arr, l, p - 1);
sort(arr, p + 1, r);
}
// 對(duì)arr[l...r]部分進(jìn)行partition操作
// 返回p, 使得arr[l...p-1] < arr[p] ; arr[p+1...r] > arr[p]
private static int partition(Integer[] arr, int l, int r) {
// 隨機(jī)在arr[l...r]的范圍中, 選擇一個(gè)數(shù)值作為標(biāo)定點(diǎn)pivot
swap(arr, l, (int) (Math.random() * (r - l + 1)) + l);
Integer v = arr[l];
int j = l; // arr[l+1...j] < v ; arr[j+1...i) > v
for (int i = l + 1; i <= r; i++) {
if (arr[i] < v) {
j++;
swap(arr, j, i);
}
}
swap(arr, l, j);
return j;
}
【注意】
當(dāng)數(shù)組中有大量重復(fù)元素的時(shí)候我們就會(huì)發(fā)現(xiàn)，此時(shí)無(wú)論我們將等于V的元素放到左邊還是右邊都會(huì)造成分配的極度不平衡，此時(shí)該算法又會(huì)退化為接近O(n^2)，如下圖所示：
三路快排
public static void sort(Integer[] array) {
_quickSort(array, 0, array.length - 1);
}
// 遞歸使用快速排序,對(duì)arr[l...r]的范圍進(jìn)行排序
public static void _quickSort(Integer[] array, int l, int r) {
if (l >= r) return;
// 隨機(jī)在arr[l...r]的范圍中, 選擇一個(gè)數(shù)值作為標(biāo)定點(diǎn)pivot
Random random = new Random();
Integer ranInt = random.nextInt(r - l + 1) + l;
swap(array, l, ranInt);
Integer e = array[l];// 比較基準(zhǔn)
int lt = l; // arr[l+1...lt] < v
int gt = r + 1; // arr[gt...r] > v
int i = l + 1; // arr[lt+1...i) == v
while (i < gt) {
if (array[i] < e) {
swap(array, i, lt + 1);
lt++;
I++;
} else if (array[i] > e) {
swap(array, i, gt - 1);
gt--;
} else {// arr[i] == v
I++;
}
}
swap(array, l, lt);
_quickSort(array, l, lt - 1);
_quickSort(array, gt, r);
}
public static void swap(Integer[] array, int l, int r) {
Integer tem = array[l];
array[l] = array[r];
array[r] = tem;
}
六、 二分查找
public static int binarySearch(Integer[] arr, Integer target){
int l = 0, r = arr.length - 1; // 在[l...r]的范圍里尋找target
while(l <= r){ // 當(dāng) l == r時(shí),區(qū)間[l...r]依然是有效的
int mid = l + (r - l) / 2;
if(arr[mid] == target) return mid;
if(target > arr[mid])
l = mid + 1; // target在[mid+1...r]中; [l...mid]一定沒(méi)有target
else // target < arr[mid]
r = mid - 1; // target在[l...mid-1]中; [mid...r]一定沒(méi)有target
}
return -1;
}
鏈表問(wèn)題
141
思路： 使用快慢指針，龜兔賽跑；
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) {
return false;
}
ListNode slow = head;
ListNode fast = head.next;
while (slow != fast) {
if (fast == null || fast.next == null) {
return false;
}
slow = slow.next;
fast = fast.next.next;
}
return true;
}
206
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while(curr != null){
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
92.
解題思路：
我們可以將反轉(zhuǎn)部分的各個(gè)節(jié)點(diǎn)頭插到反轉(zhuǎn)部分的前一個(gè)節(jié)點(diǎn)，具體做法如下：
我們需要三個(gè)指針pre、cur和next，pre指針永遠(yuǎn)指向反轉(zhuǎn)部分的前一個(gè)節(jié)點(diǎn)，cur則用來(lái)遍歷反轉(zhuǎn)部分，next永遠(yuǎn)指向cur的下一個(gè)節(jié)點(diǎn)：
第一步，先將cur的next指向next的next：
第二步，將next的next指向pre->next：
注意這里的next的next指向的一定是pre的next，而不是cur，因?yàn)閏ur的位置是一直往后走的，只有指向pre的next才是頭插。
第三步，將pre的next指向next
最后我們的cur其實(shí)并不用再往后走了。
以上操作總共需要執(zhí)行right - left次，因?yàn)橐还灿衦ight - left個(gè)節(jié)點(diǎn)需要反轉(zhuǎn)。
最后返回dumbNode的next即可
public ListNode reverseBetween(ListNode head, int m, int n) {
if(head == null) return null;
ListNode dummy = new ListNode(0); // create a dummy node to mark the head of this list
dummy.next = head;
ListNode pre = dummy; // make a pointer pre as a marker for the node before reversing
for(int i = 0; i<m-1; i++) pre = pre.next;
ListNode curr = pre.next; // a pointer to the beginning of a sub-list that will be reversed
ListNode next = null; // a pointer to a node that will be reversed
// 1 - 2 -3 - 4 - 5 ; m=2; n =4 ---> pre = 1, start = 2, then = 3
// dummy-> 1 -> 2 -> 3 -> 4 -> 5
for(int i=0; i<n-m; I++)
{
next = curr.next;
curr.next = next.next;
next.next = pre.next;
pre.next = next;
}
// first reversing : dummy->1 - 3 - 2 - 4 - 5; pre = 1, start = 2, then = 4
// second reversing: dummy->1 - 4 - 3 - 2 - 5; pre = 1, start = 2, then = 5 (finish)
return dummy.next;
}
203 移除鏈表元素
public ListNode removeElements(ListNode head, int val) {
//創(chuàng)建一個(gè)虛擬頭結(jié)點(diǎn)
ListNode dummyNode=new ListNode(val-1);
dummyNode.next=head;
ListNode prev=dummyNode;
//確保當(dāng)前結(jié)點(diǎn)后還有結(jié)點(diǎn)
while(prev.next!=null){
if(prev.next.val==val){
prev.next=prev.next.next;
}else{
prev=prev.next;
}
}
return dummyNode.next;
}
遞歸寫(xiě)法
public ListNode removeElements(ListNode head, int val) {
if(head == null) return head;
head.next = removeElements(head.next,val);
return head.val == val ? head.next : head;
}
83
public ListNode deleteDuplicates(ListNode head) {
ListNode curr = head;
while(curr != null && curr.next != null){
if(curr.val == curr.next.val){
curr.next = curr.next.next;
}else{
curr = curr.next;
}
}
return head;
}
遞歸寫(xiě)法：
public ListNode deleteDuplicates(ListNode head) {
if (head == null || head.next == null) return head;
head.next = deleteDuplicates(head.next);
return head.val == head.next.val ? head.next:head;
}
82
【思路】新建鏈表頭結(jié)點(diǎn)指針 dummy， 如果當(dāng)前節(jié)點(diǎn)cur的值與下一個(gè)節(jié)點(diǎn)的值相同，兩個(gè)節(jié)點(diǎn)都需要被刪除。為了保證刪除鏈表之后的鏈表仍然是相連的，當(dāng)前節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)pre 和后邊比cur值大的節(jié)點(diǎn)相連。
public ListNode deleteDuplicates(ListNode head) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode prev = dummy, curr = head;
while(curr != null){
while(curr.next != null && curr.val == curr.next.val){
curr = curr.next;
}
if(prev.next == curr){
prev = prev.next;
}else{
prev.next = curr.next;
}
curr = curr.next;
}
return dummy.next;
}
遞歸解法：
public ListNode deleteDuplicates (ListNode head){
if (head == null || head.next == null) return head;
if (head.val != head.next.val) {
head.next = deleteDuplicates(head.next);
return head;
} else {
while (head.next != null && head.val == head.next.val)
head = head.next;
return deleteDuplicates(head.next);
}
}
}
86
We have given a list and a value x, we have to partion the list in such that smaller value then x comes to left & greater or equals to right.
解題思路：
將所有小于給定值的節(jié)點(diǎn)取出組成一個(gè)新的鏈表，此時(shí)原鏈表中剩余的節(jié)點(diǎn)的值都大于或等于給定值，只要將原鏈表直接接在新鏈表后即可
public ListNode partition(ListNode head, int x) {
ListNode left = new ListNode(0);
ListNode right = new ListNode(0);
ListNode leftTail = left;
ListNode rightTail = right;
while(head != null){
if(head.val < x){
leftTail.next = head;
leftTail = leftTail.next;
}
else{
rightTail.next = head;
rightTail = rightTail.next;
}
head = head.next;
}
leftTail.next = right.next;
rightTail.next = null;
return left.next;
}
328
根據(jù)節(jié)點(diǎn)編號(hào)的奇偶性，我們可以將奇數(shù)節(jié)點(diǎn)和偶數(shù)節(jié)點(diǎn)分離成奇數(shù)鏈表和偶數(shù)鏈表，然后將偶數(shù)鏈表連接在奇數(shù)鏈表之后，合并后的鏈表即為結(jié)果鏈表。
具體過(guò)程如下：
1、從前往后遍歷整個(gè)鏈表，遍歷時(shí)維護(hù)四個(gè)指針：奇數(shù)鏈表頭結(jié)點(diǎn)，奇數(shù)鏈表尾節(jié)點(diǎn)，偶數(shù)鏈表頭結(jié)點(diǎn)，偶數(shù)鏈表尾節(jié)點(diǎn)。
2、遍歷時(shí)將位置編號(hào)是奇數(shù)的節(jié)點(diǎn)插在奇數(shù)鏈表尾節(jié)點(diǎn)后面，將位置編號(hào)是偶數(shù)的節(jié)點(diǎn)插在偶數(shù)鏈表尾節(jié)點(diǎn)后面。
3、遍歷完整個(gè)鏈表后，將偶數(shù)鏈表頭結(jié)點(diǎn)插在奇數(shù)鏈表尾節(jié)點(diǎn)后面即可。
public ListNode oddEvenList(ListNode head) {
if(head == null || head.next == null) return head;
ListNode oddHead = head, evenHead = head.next;
ListNode oddTail = oddHead, evenTail = evenHead;
while(evenTail != null && evenTail.next != null){
oddTail.next = oddTail.next.next;
evenTail.next = evenTail.next.next;
oddTail = oddTail.next;
evenTail = evenTail.next;
}
oddTail.next = evenHead;
return oddHead;
}
更簡(jiǎn)潔的版本：
public ListNode oddEvenList(ListNode head) {
if (head != null) {
ListNode odd = head, even = head.next, evenHead = even;
while (even != null && even.next != null) {
odd.next = odd.next.next;
even.next = even.next.next;
odd = odd.next;
even = even.next;
}
odd.next = evenHead;
}
return head;
}
2
給出兩個(gè) 非空 的鏈表用來(lái)表示兩個(gè)非負(fù)的整數(shù)。其中，它們各自的位數(shù)是按照 逆序 的方式存儲(chǔ)的，并且它們的每個(gè)節(jié)點(diǎn)只能存儲(chǔ) 一位 數(shù)字。
如果，我們將這兩個(gè)數(shù)相加起來(lái)，則會(huì)返回一個(gè)新的鏈表來(lái)表示它們的和。
您可以假設(shè)除了數(shù)字 0 之外，這兩個(gè)數(shù)都不會(huì)以 0 開(kāi)頭。
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode pre = new ListNode(0);
ListNode cur = pre;
int carry = 0;
while(l1 != null || l2 != null) {
int x = l1 == null ? 0 : l1.val;
int y = l2 == null ? 0 : l2.val;
int sum = x + y + carry;
carry = sum / 10;
sum = sum % 10;
cur.next = new ListNode(sum);
cur = cur.next;
if(l1 != null)
l1 = l1.next;
if(l2 != null)
l2 = l2.next;
}
if(carry == 1) {
cur.next = new ListNode(carry);
}
return pre.next;
}
445
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
Stack<Integer> stack1 = new Stack<>();
Stack<Integer> stack2 = new Stack<>();
while (l1 != null) {
stack1.push(l1.val);
l1 = l1.next;
}
while (l2 != null) {
stack2.push(l2.val);
l2 = l2.next;
}
int carry = 0;
ListNode head = null;
while (!stack1.isEmpty() || !stack2.isEmpty() || carry > 0) {
int sum = carry;
sum += stack1.isEmpty()? 0: stack1.pop();
sum += stack2.isEmpty()? 0: stack2.pop();
// 頭插法
ListNode node = new ListNode(sum % 10);
node.next = head;
head = node;
carry = sum / 10;
}
return head;
}
}
21 合并兩個(gè)有序鏈表
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummyHead = new ListNode(-1);
ListNode prev = dummyHead;
while(l1 != null && l2 != null){
if(l1.val <= l2.val){
prev.next = l1;
l1 = l1.next;
}else{
prev.next = l2;
l2 = l2.next;
}
prev = prev.next;
}
prev.next = l1 == null ? l2 : l1;
return dummyHead.next;
}
遞歸思路
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
}
else if (l2 == null) {
return l1;
}
else if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
}
else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
24 兩兩交換鏈表中的節(jié)點(diǎn)
解題思路：
返回值：交換完成的子鏈表
調(diào)用單元：設(shè)需要交換的兩個(gè)點(diǎn)為 head 和 next，head 連接后面交換完成的子鏈表，next 連接 head，完成交換
終止條件：head 為空指針或者 next 為空指針，也就是當(dāng)前無(wú)節(jié)點(diǎn)或者只有一個(gè)節(jié)點(diǎn)，無(wú)法進(jìn)行交換
public ListNode swapPairs(ListNode head) {
if(head == null || head.next == null){
return head;
}
ListNode next = head.next;
head.next = swapPairs(next.next);
next.next = head;
return next;
}
非遞歸寫(xiě)法：
public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode prev = dummy;
while(prev.next != null && prev.next.next != null){
ListNode curr = prev.next;
ListNode next = curr.next;
prev.next = next;
curr.next = next.next;
next.next = curr;
prev = curr;
}
return dummy.next;
}
25 k個(gè)一組翻轉(zhuǎn)鏈表
19 刪除鏈表的倒數(shù)第N個(gè)節(jié)點(diǎn)
解題思路：
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode prev = dummy,tail = dummy;
for (int i =0; i<n+1; i++){
tail = tail.next;
}
while (tail != null){
tail = tail.next;
prev = prev.next;
}
prev.next = prev.next.next;
return dummy.next;
}
第二種思路 暴力求解，遍歷鏈表獲取長(zhǎng)度
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0, head);
int length = getLength(head);
ListNode cur = dummy;
//為了與題目中的 n 保持一致，節(jié)點(diǎn)的編號(hào)從 1 開(kāi)始，頭節(jié)點(diǎn)為編號(hào) 1 的節(jié)點(diǎn)。
for (int i = 1; i < length - n + 1; ++i) {
cur = cur.next;
}
cur.next = cur.next.next;
ListNode ans = dummy.next;
return ans;
}
public int getLength(ListNode head) {
int length = 0;
while (head != null) {
length++;
head = head.next;
}
return length;
}
我們也可以在遍歷鏈表的同時(shí)將所有節(jié)點(diǎn)依次入棧。根據(jù)?！赶冗M(jìn)后出」的原則，我們彈出棧的第 n 個(gè)節(jié)點(diǎn)就是需要?jiǎng)h除的節(jié)點(diǎn)，并且目前棧頂?shù)墓?jié)點(diǎn)就是待刪除節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)。這樣一來(lái)，刪除操作就變得十分方便了。
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0, head);
Deque<ListNode> stack = new LinkedList<ListNode>();
ListNode cur = dummy;
while (cur != null) {
stack.push(cur);
cur = cur.next;
}
for (int i = 0; i < n; ++i) {
stack.pop();
}
ListNode prev = stack.peek();
prev.next = prev.next.next;
return dummy.next;
}
