目錄
1.反轉鏈表
2.鏈表的中間節點
3.找到倒數第 k 個節點
4.分割鏈表
5.洗掉鏈表中的重復節點
6.判斷回文鏈表
7.判斷鏈表是否有環
8.一個環形鏈表，回傳鏈表開始入環的第一個節點
9.找兩個鏈表相交的節點
10.合并兩個順序鏈表
1.反轉鏈表
反轉鏈表我們先從前面開始反轉，一個一個節點來
public ListNode reverseList() {
if(this.head == null) {
return null;
}
ListNode cur = this.head;
ListNode prev = null ;
ListNode curNext = cur.next;
while (cur != null) {
cur.next = prev;
prev = cur;
cur = curNext;
curNext = cur.next;
}
return prev;
}2.鏈表的中間節點
定義一個快慢指標來走，快的指標走的路程比慢的多一倍，所以慢指標指向的就是中間節點，
如果鏈表節點數是雙數則回傳第二個中間節點，如下所示
public ListNode middleNode() {
if(this.head == null) {
return null;
}
ListNode fast = this.head;
ListNode slow =this.head;
while(fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}3.找到倒數第 k 個節點
public ListNode FindKthToTail(int k) {
if(k <= 0 || head ==null) {
return null;
}
ListNode fast = this.head;
ListNode slow = this.head;
while(k-1 != 0) {
fast = fast.next;
//fast == null是防止求的倒數第k個數超出節點長度，
if(fast == null) {
return null;
}
k--;
}
while(fast.next != null) {
fast = fast.next;
slow = slow.next;
}
return slow;
}4.分割鏈表
分割鏈表，給你一個鏈表的頭節點 head 和一個特定值 x ， 使得所有 小于 x 的節點都出現在 大于或等于 x 的節點之前，
public ListNode partition(int x) {
ListNode bs = null;
ListNode be = null;
ListNode as = null;
ListNode ae = null;
ListNode cur = head;
while (cur != null) {
if(cur.val < x) {
//第一次
if(bs == null) {
bs = cur;
be = cur;
}else {
//不是第一次
be.next = cur;
be = be.next;
}
}else {
//第一次
if(as == null) {
as = cur;
ae = cur;
}else {
ae.next = cur;
ae = ae.next;
}
}
cur = cur.next;
}
//預防第一段為空
if(bs == null) {
return as;
}
be.next = as;
//預防最后一個節點的next域不為空
if(as != null) {
ae.next = null;
}
return bs;
}5.洗掉鏈表中的重復節點
升序排列的鏈表，洗掉多余重復的元素，使每個元素 只出現一次
public ListNode deleteDuplication() {
ListNode cur = head;
ListNode newHead = new ListNode(-1);
ListNode tmp = newHead;
while (cur != null) {
if(cur.next != null && cur.val == cur.next.val) {
//寫while回圈是防止有兩個以上相同的
while (cur.next != null && cur.val == cur.next.val) {
cur = cur.next;
}
// cur = cur.next;//這一步是刪完相同的節點，不留下一個
}else {
tmp.next = cur;
tmp = tmp.next;
cur = cur.next;
}
}
tmp.next = null;
return newHead.next;
}6.判斷回文鏈表
public boolean isPalindrome() {
ListNode prev = head;
ListNode fast = head;
ListNode slow = head;
//1.slow找到了中間位置
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
//2.反轉后半部分
ListNode cur = slow.next;
while (cur != null) {
ListNode curNext = cur.next;
cur.next = slow;
slow = cur;
cur = curNext;
}
//3.兩邊往中間走，判斷回文
while (prev != slow) {
if(slow.val != prev.val) {
return false;
}
if(prev.next == slow) {
return true;
}
slow = slow.next;
prev = prev.next;
}
return true;
}
7.判斷鏈表是否有環
public boolean hasCycle() {
if(head == null) return false;
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
return true;
}
}
return false;
}
8.一個環形鏈表，回傳鏈表開始入環的第一個節點
public ListNode detectCycle(ListNode head) {
if(head == null) return null;
ListNode fast = head;
ListNode slow = head;
//判斷是否有環
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
break;//相遇退出回圈
}
}
if (fast == null || fast.next == null) {
return null;
}
//頭和相遇點到環的入口點距離相等
fast = head;
while (fast != slow) {
fast = fast.next;
slow = slow.next;
}
return fast;
}9.找兩個鏈表相交的節點
兩個鏈表相交，及next 域相同
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA == null || headB == null) {
return null;
}
ListNode pl = headA;
ListNode ps = headB;
int lenA = 0;
int lenB = 0;
while (pl != null) {
lenA++;
pl = pl.next;
}
pl = headA;
while (ps != null) {
lenB++;
ps = ps.next;
}
ps = headB;
int len = lenA - lenB;
if(len < 0) {
pl = headB;
ps = headA;
len = lenB - lenA;
}
//pl走差值len步
while (len != 0) {
pl = pl.next;
len--;
}
//同時走，直到相遇
while (pl != ps) {
pl = pl.next;
ps = ps.next;
}
//回傳相遇的節點
return pl;//有值就回傳值，是空就回傳空，
}10.合并兩個順序鏈表
public static ListNode mergeTwoLists(ListNode headA,ListNode headB) {
ListNode newHead = new ListNode(-1);
ListNode tmp = newHead;
while(headA != null && headB != null) {
if(headA.val < headB.val) {
tmp.next = headA;
headA = headA.next;
tmp = tmp.next;
}else {
tmp.next = headB;
headB = headB.next;
tmp = tmp.next;
}
}
if(headA != null) {
tmp.next = headA;
}
if(headB != null) {
tmp.next = headB;
}
return newHead.next;
}轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/380206.html
標籤：其他