[알고리즘] 단일 링크 와 더 블 링크 에서 마지막 k 번 째 노드 를 삭제 합 니 다.

제목:
각각 두 개의 함 수 를 실현 합 니 다. 하 나 는 싱글 체인 시트 의 마지막 K 번 째 노드 를 삭제 할 수 있 고 다른 하 나 는 더 블 링크 의 마지막 K 번 째 노드 를 삭제 할 수 있 습 니 다.
요청:
링크 길이 가 N 이면 시간 복잡 도가 O (N) 에 달 하고 추가 공간 복잡 도 는 O (1) 에 달한다.
해답:
체인 시 계 를 처음부터 끝까지 이동 시 키 고 한 걸음 이동 할 때마다 K 수 치 를 1 로 줄 입 니 다. 체인 시계 가 끝까지 갈 때 K 수치 가 0 보다 크 면 체인 시 계 를 조정 하지 않 아 도 된다 는 것 을 설명 합 니 다. 체인 시 계 는 꼴찌 K 번 째 노드 가 없 기 때문에 이때 원래 의 체인 시 계 를 직접 돌아 가면 됩 니 다.만약 에 K 값 이 0 이 라면 링크 의 마지막 K 번 째 노드 가 바로 머리 노드 라 는 것 을 의미한다. 이때 헤드. next 로 돌아 가면 머리 노드 를 삭제 한 셈 이다.K 의 값 이 0 보다 작 을 때 다시 처음부터 걷 고 한 걸음 씩 이동 할 때마다 K 의 값 을 1 로 추가 합 니 다.K 가 0 일 때 이동 이 멈 추고 이동 한 끝 점 은 삭제 할 끝 점 의 앞 점 이다.
링크 의 길 이 는 N 이 고 마지막 K 번 째 노드 를 삭제 하려 면 마지막 K 번 째 노드 의 앞 노드 가 바로 N - K 번 째 노드 입 니 다.처음 옮 겨 다 니 면서 K 값 이 K - N 으로 바 뀌 었 다.두 번 째 옮 겨 다 닐 때 K 의 값 은 1. 0 을 추가 하면 옮 겨 다 니 는 것 을 멈 추고 있 는 위 치 는 N - K 개의 노드 의 위치 입 니 다.
프로그램:
단일 체인 테이블:

public static class Node {
  
		public int value;
  
		public Node next;
  
		public Node(int data) {
  
			this.value = data;
  
		}
  
	}
  
	public static Node removeLastKthNode(Node head, int lastKth) {
  
		if (head == null || lastKth < 1) {
  
			return head;
  
		}
  
		Node cur = head;
  
		while (cur != null) {
  
			lastKth--;
  
			cur = cur.next;
  
		}
  
		if (lastKth == 0) {
  
			head = head.next;
  
		}
  
		if (lastKth < 0) {
  
			cur = head;
  
			while (++lastKth != 0) {
  
				cur = cur.next;
  
			}
  
			cur.next = cur.next.next;
  
		}
  
		return head;
  
	}
  
더 블 링크:
public static class DoubleNode {
  
		public int value;
  
		public DoubleNode last;
  
		public DoubleNode next;
  
		public DoubleNode(int data) {
  
			this.value = data;
  
		}
  
	}
  
	public static DoubleNode removeLastKthNode(DoubleNode head, int lastKth) {
  
		if (head == null || lastKth < 1) {
  
			return head;
  
		}
  
		DoubleNode cur = head;
  
		while (cur != null) {
  
			lastKth--;
  
			cur = cur.next;
  
		}
  
		if (lastKth == 0) {
  
			head = head.next;
  
			head.last = null;
  
		}
  
		if (lastKth < 0) {
  
			cur = head;
  
			while (++lastKth != 0) {
  
				cur = cur.next;
  
			}
  
			DoubleNode newNext = cur.next.next;
  
			cur.next = newNext;
  
			if (newNext != null) {
  
				newNext.last = cur;
  
			}
  
		}
  
		return head;
  
	}