Java : 청크로 된 LinkedList 역전

Question

링크 된 목록의 헤드가 제공되고 모든 k 개의 노드 순서를 역순으로 요청할 경우 Java에서이 작업을 어떻게 수행 할 수 있습니까? 예 : k = 3 인 a->b->c->d->e->f->g->h은 c->b->a->f->e->d->h->g->f

일 것입니다. 일반적인 도움말이나 의사 코드도 크게 감사하겠습니다. 감사!

Answer 1

k이 상당히 작을 것으로 예상되는 경우 가장 단순한 것으로 간주합니다. 링크 된 목록이라는 사실을 무시하고 각 하위 시퀀스를 역순으로 배열 형식의 것으로 처리합니다.

따라서 링크 된 목록의 노드 클래스가 Node<T>이면 크기 (k)를 만듭니다. 각 세그먼트에 대해 kNodes을 배열 목록에로드 한 다음 간단한 for 루프로 요소를 반대로 만듭니다. 의사 코드에서 :

장점 : 매우 간단하고 O (N) 성능은 쉽게 인식 할 수있는 역방향 알고리즘을 이용합니다.

단점 :

는 또한이 각 Node 목록으로 이동하지 않는다는 것을 의미 있습니다 (당신이 세그먼트 당 재사용 할 수 있기 때문에, 한 번만)를 k 2N 크기 배열이 필요 만있는 오브젝트 Node는 보유 . 즉, 각 Node은 이전에 보유한 것과 다른 항목을 보유하게됩니다. 귀하의 필요에 따라 이것은 좋을 수도 있고 그렇지 않을 수도 있습니다.

Answer 2

이것은 꽤 높은 수준이지만, 몇 가지 지침을 줄 것이라고 생각합니다.

void swap3(Node first, Node last)과 같은 도우미 메서드를 사용하면 목록의 임의의 위치에서 세 개의 요소를 가져 와서 되돌릴 수 있습니다. 이것은 어렵지 않아야하며 재귀 적으로 수행 될 수 있습니다 (외부 요소 교환, 목록의 크기가 0 또는 1이 될 때까지 내부 요소에서 반복). 이제 생각해 보면 재귀를 사용하는 경우 쉽게 swapK()으로 일반화 할 수 있습니다.

일단 완료되면 연결된 목록을 따라 걸어서 k 노드마다 swapK() (으)로 전화하면됩니다. 목록의 크기가 k으로 나눌 수없는 경우 마지막 비트를 스왑하지 않거나 스와핑 기법을 사용하여 마지막 length%k 노드를 반대로 바꿀 수 있습니다.

Answer 3

TIME O (n); 공간 O (1)

목록 반전의 일반적인 요구 사항은 O (n) 시간 및 O (1) 공간에서 수행하는 것입니다. 이것은 재귀 또는 스택 또는 임시 배열 (K == n이면?) 등을 제거합니다. 그러므로 여기서의 도전 과제는 K 요소를 고려하여 내부 반전 알고리즘을 수정하는 것입니다. K 대신 거리로 dist을 사용합니다.

다음은 간단한 반전 (in-place) 반전 알고리즘입니다. 세 개의 포인터를 사용하여 목록에서 적절한 위치로 이동하십시오. b은 새 목록의 헤드를 가리 킵니다. c은 처리되지 않은 목록의 이동 헤드를 가리 킵니다. b과 c 사이의 스와핑을 용이하게하기 위해 a.

A->B->C->D->E->F->G->H->I->J->L //original 
A<-B<-C<-D E->F->G->H->I->J->L //during processing 
     ^^
      | | 
      b c 
`a` is the variable that allow us to move `b` and `c` without losing either of 
    the lists. 

Node simpleReverse(Node n){//n is head 
if(null == n || null == n.next) 
    return n; 
Node a=n, b=a.next, c=b.next; 
a.next=null; b.next=a; 
while(null != c){ 
    a=c; 
    c=c.next; 
    a.next=b; 
    b=a; 
} 
return b; 
} 

가 chunkReverse 알고리즘에 simpleReverse 알고리즘을 전환하기 위해, 다음을 수행

1] 첫번째 청크를 반전 후 bhead로 설정; head은 결과 목록의 영구 헤드입니다.

2] 다른 모든 청크의 경우 tail.next에서 b으로 설정하십시오. b은 방금 처리 된 청크의 헤드입니다.

다른 세부 사항 : 목록이 하나 개 더 적은 노드가 또는 DIST 1 이하인 경우는

3], 후 처리없이 목록을 반환한다.

4] 카운터 cnt을 사용하여 dist 개의 연속 노드가 역전 된 시점을 추적합니다.

5] 방금 처리 된 청크의 꼬리를 추적하려면 tail 변수를 사용하고 처리중인 청크의 꼬리를 추적하려면 tmp 변수를 사용하십시오.

6] 청크가 처리되기 전에, 꼬리가 될 머리가 첫 번째 노드라는 사실에 주목하십시오. 즉, 임시 꼬리 인 tmp으로 설정하십시오.

public Node reverse(Node n, int dist) { 
    if(dist<=1 || null == n || null == n.right) 
     return n; 
    Node tail=n, head=null, tmp=null; 
    while(true) { 
     Node a=n, b=a.right; n=b.right; 
     a.right=null; b.right=a; 
     int cnt=2; 
     while(null != n && cnt < dist) { 
      a=n; n=n.right; a.right=b; b=a; 
      cnt++; 
     } 
     if(null == head) head = b; 
     else { 
      tail.right=b;tail=tmp; 
     } 
     tmp=n; 
     if(null == n) return head; 
     if(null == n.right) { 
      tail.right=n; 
      return head; 
     } 
    }//true 
    } 

Answer 4

예 : 커먼 리스프

(defun rev-k (k sq) 
    (if (<= (length sq) k) 
     (reverse sq) 
     (concatenate 'list (reverse (subseq sq 0 k)) (rev-k k (subseq sq k))))) 

다른 방법에 의해 일예 F에 의해 #은 스택

open System.Collections.Generic 
let rev_k k (list:'T list) = 
    seq { 
    let stack = new Stack<'T>() 
    for x in list do 
     stack.Push(x) 
     if stack.Count = k then 
     while stack.Count > 0 do 
      yield stack.Pop() 
    while stack.Count > 0 do 
     yield stack.Pop() 
    } 
    |> Seq.toList 

Answer 5

다음을 팝업과 장소에 추가 스택을 사용하여 반복적으로 목록에서 K 항목을 제거, 스택에 밀어 사용합니다. 최선의 해결책인지는 확실치 않지만 스택은 사물을 반전시키는 적절한 방법을 제공합니다. 대기열이있는 목록 대신이 기능이 작동합니다. 간단히 디큐 K 항목을 스택에 밀어 스택에서 그들을 팝업 대기열 :

Answer 6

이 구현은 반복자 클래스 사용

LinkedList<T> list; 
//Inside the method after the method's parameters check 
ListIterator<T> it = (ListIterator<T>) list.iterator(); 
ListIterator<T> reverseIt = (ListIterator<T>) list.listIterator(k); 

for(int i = 0; i< (int) k/2; i++) 
{ 
    T element = it.next(); 
    it.set(reverseIt.previous()); 
    reverseIt.set(element); 
}