이 노트는 일주일 내내 정리되었으며 테스트는 동시에 성공적으로 실행되었습니다. 필기 테스트 및 인터뷰에 대한 정보가 있습니다.
이 기사에는 링크 된 목록의 다음 내용이 포함되어 있습니다.
1. 단일 링크 된 목록의 생성 및 횡단
2. 단일 링크 된 목록에서 노드 수를 찾으십시오.
3. 단일 링크 된 목록에서 k-last 노드를 찾으십시오 (질문 15).
4. 단일 링크 된 목록에서 중간 노드 찾기
5. 순서가 2 개의 단일 링크 된 목록을 병합하고 결합 된 링크 된 목록은 여전히 순서대로 [높은 빈도의 발생] (제안에 의한 단계, 질문 17)
6. 단일 연결 목록의 역전 [가장 높은 발생 빈도] (제안 별, 질문 16)
7. 끝에서 시작까지 단일 링크 목록을 인쇄합니다 (Sword Pointing, 제공, 질문 5)
8. 단일 링크 목록에 링이 있는지 확인
9. 링크 된 목록에서 링의 길이를 꺼냅니다.
10. 단일 링크 된 목록에서 링의 출발점을 꺼내십시오 (소드를 가리키는 칼이 제공, 질문 56). 이 질문은 위의 질문 8과 9를 사용해야합니다.
11. 두 개의 단일 연결 목록 사이의 교차점의 첫 번째 교차점을 결정하십시오 (제공하기 위해 검을 포인트, 질문 37)
1. 단일 링크 된 목록의 생성 및 횡단 :
공개 클래스 링크리스트 {public node head; 헤더 노드가 비어있는 경우 링크 된 목록이 아직 생성되지 않았다는 것을 의미합니다 Node and Behin /이 작업이 완료된 후 현재 노드가 새로 추가 된 노드를 가리 킵니다}}} // 메소드 : 링크 된 목록을 인쇄하십시오 (링크 된 목록을 인쇄하십시오. 메소드의 매개 변수는 노드 노드 공개 void print에서 트래버스가 시작됨을 나타냅니다. Node) {node == return} while (current! = null); {// 참고 : 여기에서 두 멤버 변수의 권한은 개인 권한 이이 클래스에만 액세스 할 수 있으므로 다음; data = data;} public static void main (string [] args) {linklist list = new LinkList (); );} list.print (list.head); // 헤드 노드에서 출력을 통과합니다}}위의 코드에서, 여기서 노드 노드는 내부 클래스를 사용하여이를 표현합니다 (33 행). 내부 클래스를 사용하면 가장 큰 장점은 외부 클래스로 서로 개인 작업에 액세스 할 수 있다는 것입니다.
참고 : 내부 클래스 액세스의 특성은 다음과 같습니다. 내부 클래스는 비공개 클래스를 포함하여 외부 클래스의 구성원에 직접 액세스 할 수 있습니다.
첨가 및 트래버스 작업을 용이하게하려면 LinkList 클래스에 멤버 변수 전류를 추가하여 현재 노드의 인덱스를 나타냅니다 (Line 03).
링크 된 목록 (줄 20)을 가로 지르는 방법에서, 매개 변수 노드는 노드 노드에서 시작되며 반드시 헤드 노드에서 횡단 할 필요는 없음을 의미합니다.
2. 단일 링크 된 목록에서 노드 수를 찾으십시오.
링크 된 목록이 비어 있는지 확인하기 위해주의하십시오. 시간 복잡성은 O (n)입니다. 이것은 비교적 간단합니다.
핵심 코드 :
// 방법 : 링크 된 int getLength (node head) {return int 길이 = 0; 길이 ++; current.next}};3. 단일 링크 된 목록에서 k-last 노드를 찾으십시오.
3.1 일반 아이디어 :
먼저, 전체 링크 된 목록을 처음부터 끝까지 반대하고 링크 된 목록의 길이 크기를 계산하고 링크 된 목록의 길이를 얻으십시오 링크 된 목록은 비어 있고, k는 0, k is 1, k는 링크 된 목록의 노드 수보다 큽니다.
). 시간 복잡성은 O (n)이고 일반적인 아이디어는 다음과 같습니다.
public int findlastnode (int index) {// index는 인덱스의 노드를 끝까지 나타냅니다 .// 링크 된 목록의 길이 (head == null) {return -1}; current = while! = null) {size ++; i <size -index; i ++) {current.next} return current.data;면접관이 링크 된 목록의 길이를 통과 할 수 없다면 어떻게해야합니까? 다음은.
3.2 개선 아이디어 : (이 아이디어는 다른 질문에도 사용됩니다)
여기서는 두 개의 포인터를 선언해야합니다. 즉, 두 개의 노드 유형 변수가 먼저 첫 번째 노드와 두 번째 노드가 K-1을 뒤로 이동시킵니다. 첫 번째와 두 번째는 K-1 위치로 분리 된 다음 두 노드가 마지막 노드에 도달 할 때까지 두 노드가 전체적으로 뒤로 이동합니다. 첫 번째 노드에 의해 지적되는 위치는 마지막까지 K-th의 위치입니다. 마디. 시간 복잡성은 O (n)입니다.
코드 구현 : (첫 번째 버전)
public node findlastnode (node head, int index) {node null) {reture heed; 0; i <index; second.next} = second.next;} // 두 번째 노드가 비어 있으면 먼저 뾰족한 노드가 return을 찾는 노드입니다.코드 구현 : (최종 버전) (k k가 링크 된 목록의 노드 수보다 클 때 예외를 던지기)
위의 코드에서는 기능이 구현 된 것으로 보이지만 충분히 강력하지는 않습니다.
k가 0과 같은 상황에주의를 기울이십시오.
k가 링크 된 목록의 노드 수보다 큰 경우 널 포인터 예외 가보고되므로 여기에서 판단이 필요합니다.
핵심 코드는 다음과 같습니다.
공개 Node FindlastNode (Node Head, int k) {if (k == 0 || reture null) {return node; int i = 0; i <k -1; i ++) {System.out.println ( "+i); k의 값은 이미 링크 된 목록의 길이보다 큽니다. // 링크 된 목록의 길이는 " + k보다 적습니다. NULL;}} // 두 번째 노드가 마지막 노드에 도달 할 때까지 전체적으로 움직입니다 두 번째 노드는이 시점에서 마지막 노드에 도달합니다.4. 단일 연결된 목록에서 중간 노드를 찾으십시오.
마찬가지로 면접관은 링크 된 목록의 길이를 계산할 수 없습니다.
아이디어:
위의 두 번째 섹션과 마찬가지로 두 개의 포인터가 첫 번째와 두 번째로 설정되어 있지만 여기서는 두 포인터가 동시에 앞으로 이동하고 두 번째 포인터는 매번 두 단계를 차지하고 첫 번째 포인터는 두 번째 포인터가 도달 할 때까지 매번 한 단계를 차지합니다. 마지막 노드에서, 첫 번째 포인터가 가리키는 노드는 중간 노드입니다. 링크 된 목록은 비어 있고 링크 된 목록의 노드 수는 1과 2입니다. 시간 복잡성은 O (n)입니다.
코드 구현 :
// 방법 : 링크 된 목록의 중간 노드 findmidnode (node head) {return null} node first = head; 포인트는 두 자리를 움직이고 첫 번째 노드는 하나를 움직입니다 이 시점에서, 첫 번째 포인터가 지적한 위치는 중간 노드 리턴의 위치입니다.위의 코드에서 N이 짝수 인 경우, 획득 된 중간 노드는 N/2 + 1 노드입니다. 예를 들어, 링크 된 목록에 6 개의 노드가 있으면 네 번째 노드가 얻어집니다.
5. 순서가 2 개의 단일 연결 목록을 병합하면 결합 된 링크 된 목록이 여전히 순서대로 진행됩니다.
이 질문은 종종 다양한 회사에서 조사됩니다.
예를 들어:
List 1:
1-> 2-> 3-> 4
List 2:
2-> 3-> 4-> 5
병합 후 :
1-> 2-> 2-> 3-> 3-> 4-> 4-> 5
솔루션 아이디어 :
링크 된 목록 1과 링크 된 목록 2를 비교하십시오.
이것은 병합 분류와 유사합니다. 링크 된 목록이 모두 비어 있고 그 중 하나가 비어있는 상황에 특별한주의를 기울이십시오. O (1) 공간 만 필요합니다. 시간 복잡성은 O입니다 (MAX (LEN1, LEN2))
코드 구현 :
// 두 매개 변수는 두 개의 링크 된 목록의 헤더 노드를 나타냅니다. 공개 노드 mergelinklist (node head1, node head2) {if (head1 == null && head2 == null) {// 두 링크 된 목록이 비어있는 경우}; if (head1 == null) // 처음에는 현재 노드가 Head1과 Head2의 작은 데이터를 가리 키게하고 (Head1.data <Head2.Data) {Head = Head1 = Head1; 다음; else {head = head2 = head2; // 새로운 링크 된 목록에서, 현재 포인터는 작은 데이터에 해당한다 current.next; head2 = head2 .next; (head2! = null) {// 링크 된 목록 1은 비어 있습니다.코드 테스트 :
public static void main (string [] args) {linklist1 = new LinkList (); (i); int i = 3; i <8; i ++) {list2.add (i); ); // List2를 병합하고 list3에 저장합니다 .Print (list3.head);위의 코드에 사용 된 추가 방법 및 인쇄 방법은 1 항 1과 일치합니다.
실행 효과 :
참고 :이 솔루션은 "검지가있는 제안"에서 재귀 적이며 이해하기 어려운 느낌입니다.
6. 단일 연결 목록의 역전 : [가장 높은 빈도의 발생 빈도]
예를 들어 링크 된 목록 :
1-> 2-> 3-> 4
역전 후 :
4-> 2-> 2-> 1
아이디어:
원래 링크 된 목록을 통해 처음부터 끝까지 반복하면 각 노드가 횡단되어 새로운 링크 된 목록의 프론트 엔드에 제거되어 배치됩니다. 링크 된 목록은 비어 있고 노드가 하나뿐입니다. 시간 복잡성은 O (n)입니다.
방법 1 : (Traversal)
// 메소드 : 링크 된 목록의 반전 public node reverselist (노드 헤드) {// 링크 된 목록이 비어 있거나 하나의 노드 만 있으면 반전이 필요하지 않으며 원래 링크 된 목록의 헤드 노드가 직접 반환됩니다. 원래 링크 된 if (head == null .next) {return retain} node node; 반전 후 새로운 링크 된 목록의 헤더 (current! = null) {next = current.next; 새로운 링크 된 목록의 전류 노드 Reversehead = current = 다음과 같습니다.위의 코드에서 핵심 코드는 16 행과 17 행입니다.
방법 2 : (재귀)
이 방법은 약간 어렵 기 때문에 지금은 이야기하지 않을 것입니다.
7. 단일 링크 목록을 끝에서 끝까지 인쇄합니다.
이런 종류의 거꾸로 된 순서를 위해, 우리는 먼저 스택을 먼저 생각해야합니다. 따라서이 질문은 스택을 직접 사용하거나 시스템이 스택, 즉 재귀를 사용할 수있게합니다. 링크 된 목록이 비어있는 경우에주의하십시오. 시간 복잡성은 O (n)입니다.
참고 : 먼저 링크 된 단일 목록을 뒤집는 것에 대해 생각하지 말고 출력을 가로 지르면 링크 된 목록의 구조가 파괴됩니다.
방법 1 : (스스로 새 스택 생성)
// 방법 : 끝까지 단일 링크 목록을 인쇄 공개 void reverseprint (node head) {if (head == null) {return <node> stack = new Stack <node> (); 새 스택 노드 큐어 임대료 = 링크 된 목록의 모든 노드를 누르십시오 (current! = null) // 스택을 누르면 (stack.size ()> 0) {system.out.println (stack.pop (). data);방법 2 : (시스템의 스택 사용 : 재귀, 우아하고 간결한 코드)
공개 void reverseprint (node head) {head == reverseprint (head.next);요약 : 방법 2는 재귀 구현을 기반으로합니다. Diane은 간결하고 우아하게 보이지만 링크 된 목록이 매우 길면 메소드 호출이 매우 깊어지면 스택 오버플로가 발생할 수 있습니다. 방법 1의 명시 적 스택은 루프를 기반으로 구현되며 코드는 더 강력합니다.
8. 단일 링크 목록에 링이 있는지 여부를 결정하십시오.
링크 된 목록에 링이있는 경우 두 개의 포인터가 사용됩니다.
따라서 우리는 두 개의 포인터를 사용하여 트래버스를 사용합니다. 첫 번째 포인터는 한 번에 한 단계 씩 걸으며, 두 번째 포인터는 첫 번째 포인터와 두 번째 포인터가 만나면 링이 있음을 의미합니다. 시간 복잡성은 O (n)입니다.
방법:
// 방법 : 단일 링크 된 목록에 링 공개 부울 hascycle (node head) {return false = head; ) {first = next; // 첫 번째 포인터는 second.next.next를 사용합니다. 반환 반환}} 거짓};정식 버전 코드 : (테스트 부품 포함)
여기에서는 오버로드 ADD (노드 노드) 메소드를 추가해야합니다.이 방법은 일방 통행 원형 링크 목록을 만들 때 사용해야합니다.
linklist.java : 공개 클래스 링크리스트 {public node head; LL) { / /헤더 노드가 비어있는 경우 링크 된 목록이 아직 생성되지 않았다는 것을 의미합니다. 새 노드를 만들고 현재 노드 뒤에 놓습니다 (링크 된 목록과 새 노드를 상관 시키십시오) .next = 새 노드 (data); }} // 링크 된 목록에 노드 추가 (node node) {return} if (head == null) {head = node; } current.n ext = node; Node) {node = null} node; 방법 : 단일 링크 목록에 링 퍼블릭 부울 hascycle (nod) {return false} first = head; First = first.next; // 첫 번째 포인터는 두 번째 단계를 찍습니다. 목록에는 링 리턴이 있습니다. int data; // 데이터 노드 (int data) {this.data = data; int i = 0; i <4; i ++) {list.add (i)}에 대한 데이터를 추가하십시오. 링크 된 목록의 루프입니다. 참고 :이 시점에서 얻은 고리의 구조는 다음 섹션 8에서 그림 1의 구조입니다. System.out.println (list.hascycle (list.head))}}단일 링크 된 목록에 링이 있는지 여부를 감지하는 코드는 50 행입니다.
88 행 : 링크 된 목록에 헤더 노드를 계속 추가하고 현재 링크 된 단일 목록이 반복됩니다. 최종 달리기 효과는 사실입니다.
88 줄의 코드가 삭제되면 현재 링크 된 단일 목록에는 루프가없고 실행 효과는 False입니다.
9. 링 링크 목록, 링의 길이를 꺼냅니다.
우리가 일반적으로 겪는 링크 목록은 다음과 같습니다. (그림 1)
위 그림에서 링의 길이는 4입니다.
그러나 다음도 다음과 같은 것일 수도 있습니다. (그림 2)
현재 위의 그림에서 링의 길이는 3입니다.
그렇다면 반지의 길이를 어떻게 찾습니까?
아이디어:
여기서는 먼저 위의 섹션 7에서 hascycle 메소드를 사용해야합니다 (링크 된 목록에 링이 있는지 확인하기위한 방법). 우리가 만나는 노드의 값을 반환합니다. 그런 다음이 노드가 원점으로 돌아갈 때까지 해당 노드가 내려갈 수 있어야합니다.
방법:
// 메소드 : 단일 링크 목록에 링이 있는지 여부를 결정합니다. 반환 된 노드는 공개 노드 hascycle (node head)을 충족시키는 노드입니다. {head == null) {return null = head; .next; second.next.next (첫 번째 ==) {// 링크 된 목록은 링 기반 리턴을 먼저 반환합니다 null;} /method : 링의 길이를 얻기위한 링링 된 목록이 있습니다. 매개 변수는 공개 int getCyclelength (node node)를 충족하는 노드를 나타냅니다 current.next; 길이 ++;정식 버전 코드 : (테스트 부품 포함)
공개 클래스 링크리스트 {public node current; 노드는 링크 된 목록이 아직 생성되지 않았다는 것을 의미합니다. 그런 다음 새 노드를 헤더 노드 = 새 노드 (data) {// 새 노드를 만들고; 현재 노드 (링크 된 목록과 상관 관계) current.next = 링크 된 목록의 현재 인덱스를 하나씩 움직입니다. 현재 노드는 새로 추가 된 노드를 가리 킵니다}}} // 메소드 오버로드 : 링크 된 목록에 노드를 추가하십시오 (노드 노드) {if (node == null) {return} if (head = = null). {head = node; 노드 공개 void print (node nold) {return} while (current! = null) {system.out.println (current.data); current.next; 첫 번째 = 헤드; 링크 된 목록은 먼저 반환입니다. 매개 변수는 공개 int getCyclelength (node node)를 충족하는 노드를 나타냅니다 current.next; 길이 ++; if (current == node). 개인의 권한은이 클래스에만 액세스 할 수 있기 때문에 개인. int data; // 데이터 노드 (int data) {this.data = data} {linklist list1 = new linklist (); = null; ; 프로세스는이 섹션에서 그림 2의 구조입니다. Node current = list1.hascycle (list1.head); ));}}}실행 효과 :
104 ~ 122 행의 위의 테스트 코드가 다음과 같이 변경되면 다음과 같이 변경됩니다. (즉, 그림 2의 구조를 그림 1의 구조로 변경합니다)
public static void main (string [] args) {intry list1 = int i = 0; i <4; (List1.HEAD); // 링크 된 목록에 헤더 노드를 추가하십시오 (테일 노드를 헤더 노드에 가리키는). 참고 :이 시점에서 얻은이 링의 구조는이 섹션에서 그림 1의 구조입니다. Node current = list1.hascycle (list1.head);실행 결과 :
위 코드에서 8 라인을 삭제하면 링크 된 목록에는 루프가 없으므로 실행 결과는 0입니다.
10. 단일 링크 목록에서 추출 된 링의 시작점 :
우리가 일반적으로 겪는 링크 목록은 다음과 같습니다. (그림 1)
위 그림에서 링의 시작점 1.
그러나 다음도 다음과 같은 것일 수도 있습니다. (그림 2)
이때, 위 그림에서 링의 시작점은 2입니다.
방법 1 : 방법 1
여기서 우리는 위의 섹션 8에서 링의 길이를 꺼내어 getCyclelength를 사용 하여이 방법을 사용하여 링의 길이를 얻는 방법을 사용해야합니다. 링의 길이를 얻은 후, 두 번째 포인터는 먼저 두 번째 포인터가 길이 단계로 이동해야합니다 그들이 만나면 매듭은 반지의 출발점입니다.
참고 : 링의 출발점을 찾으려면 먼저 링의 길이를 얻어야하며 링의 길이를 얻으려면 먼저 링이 있는지 여부를 결정해야합니다. 따라서 여기에는 실제로 세 가지 방법이 있습니다.
코드 구현 :
방법 1에 대한 핵심 코드 :
// 메소드 : 링의 시작점을 가져옵니다. 매개 변수 길이는 링 공개 노드 getCyclestart (int cyclelenger) {return null} first = head; (int i = 0; i <cyclelength; i ++) {second = second.next; ! = 첫 번째 = Second.next; 리턴 널;정식 버전 코드 : (테스트 부품 포함)
공개 클래스 링크리스트 {public node current; 노드는 링크 된 목록이 아직 생성되지 않았다는 것을 의미합니다. 그런 다음 새 노드를 헤더 노드 = 새 노드 (data) {// 새 노드를 만들고; 현재 노드 (링크 된 목록과 상관 관계) current.next = new Node (데이터); 현재 노드는 새로 추가 된 노드를 가리 킵니다}}} // 메소드 오버로드 : 링크 된 목록에 노드를 추가하십시오 (노드 노드) {if (node == null) {return} if (head = = null). {head = node; 노드 공개 void print (node nold) {return} while (current! = null) {system.out.println (current.data); current.next; 첫 번째 = 헤드; 링크 된 목록은 먼저 반환입니다. 매개 변수는 공개 int getCyclelength (node node)를 충족하는 노드를 나타냅니다 current.next; 길이 ++; 매개 변수 길이는 링 공개 노드 getCyclestart (int cyclelenger) {return null} first = head; (int i = 0; i <cyclelength; i ++) {second = second.next; ! = 첫 번째 = Second.next; return null;. int data; // 데이터 노드 (int data) {this.data = data} {linklist list1 = new linklist (); = null; ; 시간은이 섹션에서 Node current = list1.Hascycle (list1.head)의 구조입니다 .out.println ( "링의 시작점은" + list1.getcyclestart (list1.head, length) .data};11. 두 개의 단일 연결 목록이 교차하는 첫 번째 교차점을 결정하십시오.
"프로그래밍의 아름다움"P193, 5.3, 인터뷰 질문 37 이이 질문이 있습니다.
인터뷰 중에이 질문에 직면 할 때 많은 사람들의 첫 번째 반응은 다음과 같습니다. 두 번째 링크 목록에 노드가 첫 번째 링크 된 목록의 노드와 동일한 노드가있는 경우 두 개의 링크 된 목록 이이 노드에서 겹치는 것을 의미합니다. 분명히,이 방법의 시간 복잡성은 O (len1 * len2)입니다.
방법 1 : 스택 사용 아이디어
공통 노드와 부분적으로 겹치는 두 개의 링크 된 목록을 볼 수 있습니다. 토폴로지 모양은 Y처럼 보이지만 X 자형은 아닙니다. 아래 그림과 같이 :
위 그림과 같이 단일 링크 목록에 공통 노드가있는 경우 마지막 노드 (노드 7)는 동일해야하며 중간 (노드 6)의 특정 노드에서 시작해야합니다. 후속 노드는 동일합니다.
이제 문제는 단일 링크 된 목록에서 시작 노드에서 순서대로 횡단 할 수 있고 마지막 노드에 도달 할 수 있다는 것입니다. 도달 한 마지막 꼬리 노드는 먼저 "먼저 출구"처럼 비교됩니까? 따라서 스택의 특성을 사용 하여이 문제를 해결하는 것을 생각할 수 있습니다. 링크 된 두 목록의 노드를 두 개의 링크 된 목록의 끝 노드가 두 스택의 상단에 있습니다. 마지막 동일한 노드가 발견 될 때까지 스택의 A를 비교해 봅시다.
이러한 방식으로, 우리는 두 개의 보조 스택을 사용해야하며, 공간 복잡성은 O (Len1+Len2)이고 시간 복잡성은 O (Len1+Len2)입니다. 시작의 무차별 힘 방법과 비교하여 시간 효율이 개선되었으며, 이는 시간 효율을 위해 공간 소비를 사용하는 것과 동일합니다.
더 좋은 방법이 있습니까? 다음에 그것에 대해 이야기합시다.
방법 2 : 두 개의 링크 된 목록이 교차하는 첫 번째 노드를 결정하십시오 : Fast and Slow Pointer, 권장 (보다 최적의 솔루션)을 사용하십시오.
위의 방법 2에서 스택을 사용하는 이유는 동시에 두 개의 링크 된 목록의 끝 노드에 도달하기 위해 통과하기를 원하기 때문입니다.其实为解决这个问题我们还有一个更简单的办法：首先遍历两个链表得到它们的长度。在第二次遍历的时候，在较长的链表上走|len1-len2| 步，接着再同时在两个链表上遍历，找到的第一个相同的结点就是它们的第一个交点。
这种思路的时间复杂度也是O(len1+len2)，但是我们不再需要辅助栈，因此提高了空间效率。当面试官肯定了我们的最后一种思路的时候，就可以动手写代码了。
核心代码：
//方法：求两个单链表相交的第一个交点public Node getFirstCommonNode(Node head1, Node head2) { if (head1 == null || head == null) { return null; } int length1 = getLength(head1); int length2 = getLength(head2); int lengthDif = 0; //两个链表长度的差值Node longHead; Node shortHead; //找出较长的那个链表if (length1 > length2) { longHead = head1; shortHead = head2; lengthDif = length1 - length2; } else { longHead = head2; shortHead = head1; lengthDif = length2 - length1; } //将较长的那个链表的指针向前走length个距离for (int i = 0; i < lengthDif; i++) { longHead = longHead.next; } //将两个链表的指针同时向前移动while (longHead != null && shortHead != null) { if (longHead == shortHead) { //第一个相同的结点就是相交的第一个结点return longHead; } longHead = longHead.next; shortHead = shortHead.next; } return null; } //方法：获取单链表的长度public int getLength(Node head) { if (head == null) { return 0; } int length = 0; Node current = head; while (current != null) { length++; current = current.next; } return length;以上就是有关java链表的经典面试题目，希望可以帮助大家顺利通过面试。