方法一：好理解，但是需要遍歷三次鏈表

/*** 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 swapNodes(ListNode head, int k) {ListNode ahead = new ListNode(0,head);ListNode current = ahead;ListNode topK = new ListNode(0,null);ListNode botK = new ListNode(0,null);int count = 0;//第一次遍歷，找到正數(shù)第K個(gè)節(jié)點(diǎn)，然后用一個(gè)新的節(jié)點(diǎn)暫存信息，同時(shí)求得總節(jié)點(diǎn)個(gè)數(shù)while(current.next!=null){count++;current = current.next;if(count==k){topK.val = current.val;topK.next = current.next;}}//count為總節(jié)點(diǎn)個(gè)數(shù)//第二次遍歷找到倒數(shù)第K個(gè)節(jié)點(diǎn)，然后用一個(gè)新的節(jié)點(diǎn)暫存信息//正數(shù)是k,倒數(shù)換成正數(shù)就應(yīng)該是鏈表的長度-k+1current = ahead;int increase = 0;while(current.next!=null){increase++;current = current.next;//找到倒數(shù)第K個(gè)節(jié)點(diǎn)，然后用一個(gè)新的節(jié)點(diǎn)暫存信息if(increase ==(count+1-k)){botK.val = current.val;botK.next = current.next;}}current = ahead;int num = 0;//第三次遍歷，交換兩個(gè)節(jié)點(diǎn)while(current.next!=null){num++;current = current.next;if(num==k){current.val= botK.val;//current.next=current.next;//僅僅是交換的節(jié)點(diǎn)的val值}if(num==(count+1-k)){current.val=topK.val;//current.next=current.next;}}return ahead.next;} }

方法二，值遍歷一次，但是要注意指針的挪動(dòng)次數(shù)關(guān)系的理解

/**聲明三個(gè)節(jié)點(diǎn)cur、first、last全部指向head節(jié)點(diǎn)利用current從頭結(jié)點(diǎn)開始遍歷鏈表，topK指針移動(dòng)k - 1步后定位至該鏈表正數(shù)第k個(gè)節(jié)點(diǎn),設(shè)鏈表的節(jié)點(diǎn)個(gè)數(shù)為nums，當(dāng)first指針指向第k個(gè)節(jié)點(diǎn)時(shí)，此時(shí)鏈表還有nums - k個(gè)節(jié)點(diǎn)沒有遍歷。因?yàn)殒湵淼念^節(jié)點(diǎn)到倒數(shù)第k個(gè)節(jié)點(diǎn)之間的節(jié)點(diǎn)個(gè)數(shù)剛好也是nums - k個(gè)，所以當(dāng)遍歷到正數(shù)第k個(gè)節(jié)點(diǎn)后，botK指針開始從head節(jié)點(diǎn)移動(dòng)nums - k步后即指向了倒數(shù)第k個(gè)節(jié)點(diǎn)。 */ class Solution {public ListNode swapNodes(ListNode head, int k) {ListNode current = head;ListNode topK = head;ListNode botK = head;int count = 1;while(current.next!=null){ if(count<k){topK = topK.next;}else{botK = botK.next;}count++;current = current.next;}//交換兩個(gè)節(jié)點(diǎn)int temp = topK.val;topK.val = botK.val;botK.val = temp;return head;} }

總結(jié)

以上是生活随笔為你收集整理的LeetCode——1721.交换链表中的节点的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。