鏈表的基本操作
定義
class Node{
Item item;//表示任意的數(shù)據(jù)類(lèi)型
Node next;//指向下一個(gè)節(jié)點(diǎn)的引用
}
從鏈表頭部插入元素
Node oldFirst = first;//oldFirst指向原來(lái)的頭結(jié)點(diǎn)
first = new Node();
first.item = item;
first.next = oldFirst;
從鏈表頭部刪除元素
first = first.next; //first指向first.next即可
從鏈表尾部插入元素
Node oldLast = last;
last = new Node();
last.item = item;
oldLast.next = last;
從中間插入和刪除結(jié)點(diǎn)
Node first = new Node();
Node third = new Node();
first.next = third;
//在first和second之間插入second
Node second = new Node();
first.next = second;
second.next = third;
//刪除second結(jié)點(diǎn)(刪除結(jié)點(diǎn)必須知道前一個(gè)結(jié)點(diǎn))
first.next = third;
棧和對(duì)列的實(shí)現(xiàn)
棧的實(shí)現(xiàn)
使用數(shù)組實(shí)現(xiàn)棧
public class ArrayStack<Item> implements Iterable<Item>{
//初始化數(shù)組的大小
private Item[] arr = (Item[])new Object[5];
private int N == 0;
public int size(){
return N;
}
public boolean isEmpty(){
return N == 0 ? true : false;
}
public void push(Item item){
if(N == arr.length){
resize(2*N);
}
arr[N++] = item;
}
public Item pop(){
Item item = arr[--N];
arr[N] = null;
if(N > 0 && N == arr.length/4){
resize(2*N);
}
return item;
}
//動(dòng)態(tài)調(diào)整數(shù)組大小
public void resize(int capacity){
Item[] temp = (Item[])new Object[capacity];
for(int i = 0; i < N; i++){
temp[i] = arr[i];
}
arr = temp;
}
//實(shí)現(xiàn)迭代器功能齐佳,可以使用foreach語(yǔ)句
public Iterator<Item> iterator(){
return new ArrayReverseIterator();
}
private class ArrayReverseIterator implements Iterator<Item>{
private int index = N;
public boolean hasNext(){
return N > 0 ? true : false;
}
public Item next(){
return arr[--N];
}
}
}
使用鏈表實(shí)現(xiàn)棧
public class NodeStack<Item> implements Iterable<Item> {
private class Node{
Item item;
Node next;
}
private Node first;
private int N = 0;
public void push(Item item){
Node oldfirst = first;
first = new Node();
first.item = item;
first.next = oldfirst;
N++;
}
public Item pop(){
Item item = first.item;
first = first.next;
N--;
return item;
}
public boolean isEmpty(){
return N == 0;
}
public int size(){
return N;
}
@Override
public Iterator<Item> iterator() {
return new ListIterator();
}
private class ListIterator implements Iterator<Item>{
private Node current = first;
@Override
public boolean hasNext() {
return current != null;
}
@Override
public Item next() {
Item item = current.item;
current = current.next;
return item;
}
}
}
隊(duì)列的實(shí)現(xiàn)
public class Queue<Item> implements Iterable<Item>{
private class Node{
Item item;
Node next;
}
Node first;
Node last;
private int N = 0;
public boolean isEmpty(){
return N == 0;
}
public int size(){
return N;
}
public void enqueue(Item item){
Node oldLast = last;
last = new Node();
last.item = item;
if(isEmpty()){
first = last;
}else{
oldLast.next = last;
}
N++;
}
public Item dequeue(){
Item item = first.item;
first = first.next;
if(isEmpty()){
last = null;
}
N--;
return item;
}
public Iterator<Item> iterator(){
return new QueueIterator();
}
private class QueueIterator implements Iterator<Item>{
private Node current = first;
public boolean hasNext(){
return current != null;
}
public Item next(){
Item item = current.item;
current = current.next;
return item;
}
}
}
鏈表練習(xí)題目
1.有一個(gè)整數(shù)val留晚,如何在節(jié)點(diǎn)值有序的環(huán)形鏈表中插入一個(gè)節(jié)點(diǎn)值為val的節(jié)點(diǎn),并且保證這個(gè)環(huán)形單鏈表依然有序.給定鏈表的信息吼蚁,及元素的值A(chǔ)及對(duì)應(yīng)的nxt指向的元素編號(hào)同時(shí)給定val岳枷,請(qǐng)構(gòu)造出這個(gè)環(huán)形鏈表,并插入該值。
class ListNode{
int val;
ListNode next;
public ListNode(int val){
this.val = val;
}
}
public ListNode insert(int[] A, int[] next, int val){
if(A == null || A.length == 0){
ListNode node = new ListNode(val);
return node;
}
ListNode head = new ListNode(A[0]);
ListNode point = head;
ListNode current = null;
//通過(guò)數(shù)組構(gòu)造鏈表
for(int i = 0; i < next.length - 1; i++){
current = new ListNode(A[next[i]]);
ponit.next = current;
point = current;
}
if(val < head.val){
ListNode node = new ListNode(val);
node.next = head;
head = node;
return head;
}
if(val > current.val){
ListNode node = new ListNode(val);
current.next = node;
return head;
}
ListNode p1 = head;
ListNode p2 = head.next;
while(p1 != null && p2 != null){
if(p1.val <= val && val <= p2.val){
ListNode node = new ListNode(val);
p1.next = node;
node.next = p2;
return head;
}else{
p1 = p1.next;
p2 = p2.next;
}
}
return head;
}
2.實(shí)現(xiàn)一個(gè)算法跺株,刪除單向鏈表中間的某個(gè)結(jié)點(diǎn),假定你只能訪問(wèn)該結(jié)點(diǎn)脖卖。給定帶刪除的節(jié)點(diǎn)乒省,請(qǐng)執(zhí)行刪除操作,若該節(jié)點(diǎn)為尾節(jié)點(diǎn)畦木,返回false袖扛,否則返回true.
public boolean remove(ListNode pNode){
if(pNode.next == null){
return false;
}
pNode.val = pNode.next.val;
pNode.next = pNode.next.next;
return true;
}
3.對(duì)于一個(gè)鏈表,我們需要用一個(gè)特定閾值完成對(duì)它的分化十籍,使得小于等于這個(gè)值的結(jié)點(diǎn)移到前面蛆封,大于該值的結(jié)點(diǎn)在后面,同時(shí)保證兩類(lèi)結(jié)點(diǎn)內(nèi)部的位置關(guān)系不變勾栗。給定一個(gè)鏈表的頭結(jié)點(diǎn)head惨篱,同時(shí)給定閾值val,請(qǐng)返回一個(gè)鏈表围俘,使小于等于它的結(jié)點(diǎn)在前砸讳,大于等于它的在后,保證結(jié)點(diǎn)值不重復(fù)界牡。
public ListNode listDivide(ListNode head,int val){
public ListNode head_1 = null;
public ListNode tail_1 = null;
public ListNode head_2 = null;
public ListNode tail_2 = null;
public ListNode next = null;
while(head != null){
next = head.next;
head.next = null;
if(head.val <= val){
ListNode oldTail_1 = tail_1;
tail_1 = head;
if(head_1 == null){
head_1 = tail_1;
}else{
oldtail_1.next = tail_1;
}
}else if(head.val > val){
ListNode oldTail_2 = tail_2;
tail_2 = head;
if(head_2 == null){
head_2 = tail_2;
}else{
oldTail_2.next = tail_2;
}
}
head = next;
}
if(tail_1 != null){
tail_1.next = head_2;
}
return head_1 != null ? head_1 : head_2;
}
4.有一個(gè)單鏈表绣夺,請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法,使得每K個(gè)節(jié)點(diǎn)之間逆序欢揖,如果最后不夠K個(gè)節(jié)點(diǎn)一組陶耍,則不調(diào)整最后幾個(gè)節(jié)點(diǎn)。例如鏈表1->2->3->4->5->6->7->8->null她混,K=3這個(gè)例子烈钞。調(diào)整后為,3->2->1->6->5->4->7->8->null坤按。因?yàn)镵==3毯欣,所以每三個(gè)節(jié)點(diǎn)之間逆序,但其中的7臭脓,8不調(diào)整酗钞,因?yàn)橹挥袃蓚€(gè)節(jié)點(diǎn)不夠一組。
public ListNode inverse(ListNode head,int k){
if(head == null || head.next == null || k < 2){
return head;
}
ListNode pre = null;
ListNode current = head;
ListNode start = null;
ListNode next = null;
int count = 1;
while(current != null){
next = current.next;
if(count == 3){
start = pre == null ? head : pre.next;
head = pre == null ? current : head;
reverse(pre,start,current,next);
pre = start;
count = 0;
}
count++;
current = next;
}
return head;
}
//先逆序k個(gè)節(jié)點(diǎn)
public void reverse(ListNode left,ListNode start,ListNode end,ListNode right){
ListNode current = start.next;
ListNode point = start;
ListNode next = null;
while(current != right){
next = current.next;
current.next = point;
point = current;
current = next;
}
if(left != null){
left.next = end;
}
start.next = right;
}
5.如何判斷一個(gè)單鏈表是否有環(huán)?有環(huán)的話返回進(jìn)入環(huán)的第一個(gè)節(jié)點(diǎn)的值砚作,無(wú)環(huán)的話返回-1窘奏。
public int chkLoop(ListNode head, int adjust) {
if(head == null){
return -1;
}
boolean isCircle = false;
ListNode fast = head;
ListNode slow = head;
while(slow != null && fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
if(slow == fast){
isCircle = true;
break;
}
}
if(!isCircle){
return -1;
}
fast = head;
while(slow != fast){
slow = slow.next;
fast = fast.next;
}
return slow.val;
}
6.現(xiàn)在有兩個(gè)無(wú)環(huán)單鏈表,若兩個(gè)鏈表的長(zhǎng)度分別為m和n葫录,請(qǐng)?jiān)O(shè)計(jì)一個(gè)時(shí)間復(fù)雜度為O(n + m)着裹, 額外空間復(fù)雜度為O(1)的算法,判斷這兩個(gè)鏈表是否相交米同。
public boolean chkIntersect(ListNode headA, ListNode headB) {
if(headA == null || headB == null){
return false;
}
boolean isIntersect = false;
int lenA = 0;
ListNode p1 = headA;
while(p1 != null){
p1 = p1.next;
lenA++;
}
int lenB = 0;
ListNode p2 = headB;
while(p2 != null){
p2 = p2.next;
lenB++;
}
if(lenA >= lenB){
isIntersect = isCrossing(headA,headB,lenA - lenB);
}else{
isIntersect = isCrossing(headB,headA,lenB - lenA);
}
return isIntersect;
}
public boolean isCrossing(ListNode headA, ListNode headB, int num){
ListNode curA = headA;
boolean isCross = false;
while(num != 0){
curA = curA.next;
num--;
}
ListNode curB = headB;
while(curA != null && curB != null){
if(curA == curB){
isCross = true;
break;
}
curA = curA.next;
curB = curB.next;
}
return isCross;
}
7.如何判斷兩個(gè)有環(huán)單鏈表是否相交骇扇?相交的話返回第一個(gè)相交的節(jié)點(diǎn),不想交的話返回空面粮。
public boolean chkInter(ListNode head1, ListNode head2, int adjust0, int adjust1) {
if(head1 == null || head2 == null){
return false;
}
ListNode p1 = insert(head1);
ListNode p2 = insert(head2);
//入環(huán)節(jié)點(diǎn)相交
if(p1 == p2){
return true;
}
//環(huán)中相交
ListNode start1 = p1.next;
while(start1 != p1){
if(start1 == p2){
return true;
}
start1 = start1.next;
}
return false;
}
//入環(huán)節(jié)點(diǎn)
public ListNode insert(ListNode head){
ListNode slow = head;
ListNode fast = head;
while(slow != null && fast != null){
slow = slow.next;
fast = fast.next.next;
if(slow == fast){
break;
}
}
fast = head;
while(slow != fast){
slow = slow.next;
fast = fast.next;
}
return slow;
}