劍指offer計劃鏈表
從尾到頭列印鏈表
/**
* public class ListNode {
* int val;
* ListNode next = null;
*
* ListNode(int val) {
* this.val = val;
* }
* }
*
*/
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> num = new ArrayList();
ArrayList<Integer> res = new ArrayList();
while(listNode!=null){
num.add(listNode.val);
listNode=listNode.next;
}
for(int i = num.size()-1;i>=0; i --){
res.add(num.get(i));
}
return res;
}
}
反轉鏈表
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode ReverseList(ListNode head) {
if(head==null) return null;
ListNode pre = null;
while(head!=null){
ListNode next=head.next;
head.next=pre;
pre = head;
head = next;
}
return pre;
}
}
合并兩個排序的鏈表
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
if(list1==null) return list2;
if(list2==null) return list1;
if(list1.val<=list2.val) {
list1.next=Merge(list1.next,list2);
return list1;}
else {
list2.next=Merge(list1,list2.next);
return list2;}
}
}
兩個鏈表的第一個公共結點
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
import java.util.HashSet;
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
HashSet<ListNode> hashset = new HashSet<ListNode>();
if(pHead1==null || pHead2==null) return null;
while(pHead1!=null) {
hashset.add(pHead1);
pHead1= pHead1.next;
}
while(pHead2!=null){
if(hashset.contains(pHead2)) return pHead2;
pHead2= pHead2.next;
}
return null;
}
}
鏈表中環的入口結點
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
*/
import java.util.*;
public class Solution {
public ListNode EntryNodeOfLoop(ListNode pHead) {
HashSet<ListNode> hashset = new HashSet();
while(pHead!=null){
if(hashset.contains(pHead)){
return pHead;
}
hashset.add(pHead);
pHead = pHead.next;
}
return null;
}
}
鏈表中倒數最后k個結點
public ListNode FindKthToTail(ListNode pHead, int k) {
if (pHead == null || k == 0) {
return null;
}
int count = 0;
ListNode temp = pHead;
while (temp!=null) {
count ++ ;
temp = temp.next;
}
if (count < k) {
return null;
}
temp = pHead;
for (int i = 0; i < count - k; i++) {
temp = temp.next;
}
return temp;
}
復雜鏈表的復制
/*
public class RandomListNode {
int label;
RandomListNode next = null;
RandomListNode random = null;
RandomListNode(int label) {
this.label = label;
}
}
*/
import java.util.*;
public class Solution {
Map<RandomListNode, RandomListNode> cachedNode = new HashMap<RandomListNode, RandomListNode>();
public RandomListNode Clone(RandomListNode pHead) {
if (pHead == null) return null;
if (!cachedNode.containsKey(pHead)) {
RandomListNode headNew = new RandomListNode(pHead.label);
cachedNode.put(pHead, headNew);
headNew.next = Clone(pHead.next);
headNew.random = Clone(pHead.random);
}
return cachedNode.get(pHead);
}
}
洗掉鏈表中重復的結點
public class Solution {
public ListNode deleteDuplication(ListNode pHead) {
if (pHead == null || pHead.next == null) { // 只有0個或1個結點，則回傳
return pHead;
}
if (pHead.val == pHead.next.val) { // 當前結點是重復結點
ListNode pNode = pHead.next;
while (pNode != null && pNode.val == pHead.val) {
// 跳過值與當前結點相同的全部結點,找到第一個與當前結點不同的結點
pNode = pNode.next;
}
return deleteDuplication(pNode); // 從第一個與當前結點不同的結點開始遞回
} else { // 當前結點不是重復結點
pHead.next = deleteDuplication(pHead.next); // 保留當前結點，從下一個結點開始遞回
return pHead;
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/309390.html
標籤：其他