앞장 서지 않 는 양 방향 링크 실현
6699 단어 데이터 구조
package jing.able.dao;
import jing.able.impl.IDoubleLinked;
/**
* @author panjing
* @describe:
* @date 2019/4/7
* @time 12:03
*/
public class DoubleLinkList implements IDoubleLinked {
class Node {
private int data; //
private Node prev;//
private Node next;//
public Node(int data) {
this.data = data;
this.next = null;
this.prev = null;
}
}
private Node head;
private Node last; //last
public DoubleLinkList() {
this.head = null;
this.last = null;
}
@Override
public void addFirst(int data) {
Node node = new Node(data);
if (head == null) { //
this.head = node;
this.last = node;
} else {
node.next = this.head;
node.next.prev = node;
this.head = node;
}
}
@Override
public void addLast(int data) {
Node node = new Node(data);
if (head == null) { //
this.head = node;
this.last = node;
} else {
this.last.next = node;
node.prev = this.last;
this.last = node;
}
}
private Node seachIndex(int index) {
cheackIndex(index);
Node cur = this.head;
int count = 0;
while (count < index) {
cur = cur.next;
count++;
}
return cur;
}
private void cheackIndex(int index) {
if (index < 0 || index > getLength()) {
throw new UnsupportedOperationException(" ");
}
}
@Override
public boolean addindex(int index, int data) {
if (index == 0) {
addFirst(data);
return true;
}
if (index == getLength()) {
addLast(data);
return true;
}
Node node = new Node(data);
Node cur = seachIndex(index);
node.next = cur;
cur.prev.next = node;
node.prev = cur.prev;
cur.prev = node;
return true;
}
@Override
public boolean contains(int key) {
Node cur = this.head;
while (cur != null) {
if (cur.data == key) {
return true;
}
cur = cur.next;
}
return false;
}
@Override
public int remove(int key) {
Node cur = this.head;
while (cur != null) {
if (cur.data == key) {
int oldData = cur.data;
//
if (cur == this.head) {
this.head = this.head.next;
this.head.prev = null;
} else {
//
cur.prev.next = cur.next;
if (cur.next != null) {
cur.next.prev = cur.prev;
} else {
// ,last
this.last = cur.prev;
}
}
return oldData;
}
cur = cur.next;
}
return -1;
}
@Override
public void removeAllKey(int key) {
Node cur = this.head;
while (cur != null) {
if (cur.data == key) {
//
if (cur == this.head) {
this.head = this.head.next;
this.head.prev = null;
} else {
//
cur.prev.next = cur.next;
if (cur.next != null) {
cur.next.prev = cur.prev;
} else {
// ,last
this.last = cur.prev;
}
}
}
cur = cur.next;
}
}
@Override
public int getLength() {
int count = 0;
Node cur = this.head;
while (cur != null) {
count++;
cur = cur.next;
}
return 0;
}
@Override
public void display() {
Node cur = this.head;
while (cur != null) {
System.out.println(cur.data + " ");
cur = cur.next;
}
}
@Override
public void clear() {
while (this.head != null) {
Node cur = this.head.next;
this.head.next = null;
head.prev = null;
head = cur;
this.last = null;
}
}
public Node middleNode(Node head) {
Node cur = this.head;
int len = getLength() / 2;
for (int i = 0; i < len; i++) {
cur = cur.next;
}
return cur;
}
public class Solution {
public Node FindKthToTail(Node head, int k) {
Node cur = head;
Node fast = head;
Node slow = head;
int len = 0;
while (cur != null) {
len++;
cur = cur.next;
}
if (fast == null || k <= 0 || k > len) {
return null;
}
for (int i = 0; i < k; i++) {
fast = fast.next;
}
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
}
public Node mergeTwoLists(int x) {
Node beforStart = null;
Node beforEnd = null;
Node afterStart = null;
Node afterEnd = null;
Node pHead = this.head;
while (pHead != null) {
Node pHeadNext = pHead.next;
pHead.next = null;
if (pHead.data < x) {
if (beforStart == null) {
beforStart = pHead;
beforEnd = beforStart;
} else {
beforEnd.next = pHead;
beforEnd = beforEnd.next;
}
} else {
if (pHead.data > x) {
if (afterStart == null) {
afterStart = pHead;
afterEnd = afterStart;
} else {
afterEnd.next = pHead;
afterEnd = afterEnd.next;
}
}
pHead = pHeadNext;
}
if (beforStart == null ){
return afterStart;
}
beforEnd.next = afterStart;
return beforStart;
}
return beforStart;
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.