연결리스트란?

  • 데이터를 링크로 연결해서 관리하는 자료구조
  • 자료의 순서는 정해져 있지만, 메모리상 연속성이 보장되지는 않음

연결리스트의 장점

  • 데이터 공간을 미리 할당할 필요 없음
  • 즉, 리스트의 길이가 가변적이라 데이터 추가와 삭제가 용이함

연결리스트의 단점

  • 연결구조를 위한 별도 데이터 공간 필요
  • 연결정보를 찾는 시간이 필요 (배열에 비해 접근 속도가 상대적으로 느림)
  • 데이터 추가, 삭제 시 앞뒤 데이터의 연결을 재구성하는 작업 필요

연결리스트의 기본 구조

노드(Node)
데이터 저장 단위로, 값과 포인터로 구성됨.

포인터(Pointer)
다음 노드나 이전 노드의 연결 정보

포인터로 연결 리스트 만들기

리스트에 데이터를 삽입할 때 노드용 객체를 만들고 삭제할 때 노드용 객체를 없애면 배열로 리스트를 만들 때 발생하는 문제를 해결 할 수 있다. 이런 노드를 구현하는 것이 클래스 Node<E>이다.
Node<E>는 데이터용 필드인 data와 별도로 자기 자신과 같은 클래스형의 인스턴스를 참조하는(가리키는) 참조용 필드 next를 가진다. 이런 클래스 구조를 자기 참조형이라고 한다.

Java에서는 일반적으로 다음과 같은 형태로 Node<E>클래스를 정의합니다.

class Node<E> {
    E data;
    Node<E> next;

    public Node(E data) {
        this.data = data;
        this.next = null;
    }
}

제네릭 타입이란?👈
위 코드에서는 제네릭 타입(E)을 사용하여 데이터(data)의 타입을 지정한다.
또한, 다음 노드를 가리키는 포인터(next)도 Node<E>타입으로 지정한다.

Node<E>클래스는 연결 리스트를 구현할 때 매우 중요한 역할을 한다.
각 노드를 나타내는 Node<E>클래스를 정의하고, 다음 노드를 가리키는 포인터를 사용하여 노드들을 서로 연결함으로써 연결 리스트를 구현할 수 있다.

연결리스트의 시간복잡도

  1. 삽입과 삭제 연산의 시간 복잡도
    단일 연결 리스트에서 헤드에 노드를 삽입하거나 삭제하는 경우 O(1)의 시간 복잡도를 갖는다.
    단일 연결 리스트에서 마지막 노드에 노드를 삽입하는 경우 O(n)의 시간 복잡도를 갖는다.
    이는 마지막 노드를 찾아야 하기 때문이다.

  2. 탐색 연산의 시간 복잡도
    단일 연결 리스트에서 특정 노드를 찾는 경우 O(n)의 시간 복잡도를 갖는다.
    이는 노드를 찾을 때마다 전체 리스트를 탐색해야 하기 때문이다.

따라서, Linked List에서 연산의 시간 복잡도는 주로 삽입, 삭제, 탐색 연산에서의 연산 횟수와 연관이 있기 때문에, 이를 고려하여 적절한 자료구조 선택이 필요하다.

연결리스트의 기본 연산

  1. 데이터 추가
    데이터 추가 위치 (head,중간,tail)에 따른 연결 작업 필요



  1. 데이터 삭제
    데이터 삭제 위치 (head,중간,tail)에 따른 연결 작업 필요
    실제로는 head 이전 작업만 하면 java에서 알아서 나머지를 처리한다.



백엔드스쿨 연결리스트 기본 구조 구현 소스 (단순 연결 리스트)

// 선형 자료구조 - 연결 리스트
// 단순 연결 리스트 (simple ver.) 기본 구조 구현

// 노드
class Node {
    int data;
    Node next;

    Node() {}  // 생성자
    Node(int data, Node next) {
        this.data = data;
        this.next = next;
    }
}

class LinkedList {
    Node head;

    LinkedList() {} // 생성자
    LinkedList(Node node) {
        this.head = node;
    }

    //  연결 리스트 비어있는지 확인
    public boolean isEmpty() {
        if (this.head == null) {
            return true;
        }
        return false;
    }

    //  연결 리스트의 맨 뒤에 데이터 추가
    public void addData(int data) {
        if (this.head == null) {  // head에 아무것도 없을 때
            this.head = new Node(data, null);  // 해당 data추가
        } else {  // 만약 node들이 있으면
            Node cur = this.head; // head부터 node들을 하나씩 순회
            while (cur.next != null) {
                cur = cur.next;
            }
            cur.next = new Node(data, null); // 가장 끝에 node를 만들고 data추가
        }
    }

    //  연결 리스트의 맨 뒤의 데이터 삭제
    public void removeData() {
        if (this.isEmpty()) {
            System.out.println("List is empty");
            return;
        }

        Node cur = this.head;
        Node prev = cur;

        while (cur.next != null) {
            prev = cur;
            cur = cur.next;
        }

        if (cur == this.head) {
            this.head = null;
        } else {
            prev.next = null;
        }
    }

    //  연결 리스트에서 데이터 찾기
    public void findData(int data) {
        if (this.isEmpty()) {
            System.out.println("List is empty");
            return;
        }

        Node cur = this.head;
        while (cur != null) {
            if (cur.data == data) {
                System.out.println("Data exist!");
                return;
            }
            cur = cur.next;
        }
        System.out.println("Data not found!");
    }

    //  연결 리스트의 모든 데이터 출력
    public void showData() {
        if (this.isEmpty()) {
            System.out.println("List is empty!");
            return;
        }

        Node cur = this.head;
        while (cur != null) {
            System.out.print(cur.data + " ");
            cur = cur.next;
        }
        System.out.println();
    }
}


public class Main {

    public static void main(String[] args) {

//      Test Code
        LinkedList myList = new LinkedList(new Node(1, null));
        myList.showData();      // 1

        myList.addData(2);
        myList.addData(3);
        myList.addData(4);
        myList.addData(5);
        myList.showData();      // 1 2 3 4 5

        myList.findData(3);     // Data exist!
        myList.findData(100);   // Data not found!

        myList.removeData();
        myList.removeData();
        myList.removeData();
        myList.showData();      // 1 2

        myList.removeData();
        myList.removeData();
        myList.removeData();    // List is empty

    }

}

Chat-GPT 예제소스

중간에 값 추가

import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        // LinkedList 객체 생성
        LinkedList<Integer> list = new LinkedList<>();

        // 데이터 삽입
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);

        // 3과 4 사이에 6 삽입
        list.add(3, 6);  // index 3번째자리에, 6을 넣음

        // 데이터 출력
        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i) + " ");
        }
    }
}

특정 데이터 삭제

import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        // LinkedList 객체 생성
        LinkedList<Integer> list = new LinkedList<>();
        
        // 데이터 삽입
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(2);
        list.add(4);
        list.add(1);
        
        // 삭제할 데이터
        int target = 2;
        
        // 데이터 삭제
        for (int i = 0; i < list.size(); i++) {
            if (list.get(i).equals(target)) {
                list.remove(i);
                i--;
            }
        }
        
        // 데이터 출력
        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i) + " ");
        }
    }
}

위의 예시 코드에서는 먼저 LinkedList 객체를 생성하고, 여러 개의 데이터를 삽입한다.
이후 삭제할 데이터를 변수 target에 저장하고, 반복문을 통해 linked list의 모든 데이터를 검색한다.

검색한 데이터와 현재 데이터가 같으면 해당 데이터를 remove() 메서드를 사용하여 삭제하고,
변수 i 값을 1 감소시켜 검색할 범위를 조정한다.
이렇게 검색된 모든 데이터를 삭제한 후에는 반복문을 통해 linked list의 데이터를 출력한다.


중복된 데이터 제거

import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        // LinkedList 객체 생성
        LinkedList<Integer> list = new LinkedList<>();
        
        // 데이터 삽입
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(2);
        list.add(4);
        list.add(1);
        
        // 중복된 데이터 제거
        for (int i = 0; i < list.size(); i++) {
            for (int j = i + 1; j < list.size(); j++) {
                if (list.get(i).equals(list.get(j))) {
                    list.remove(j);
                    j--;
                }
            }
        }
        
        // 데이터 출력
        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i) + " ");
        }
    }
}

위의 예시 코드에서는 먼저 LinkedList 객체를 생성하고, 여러 개의 데이터를 삽입한다.
중복된 데이터를 제거하기 위해서는 먼저 첫 번째 for문에서 리스트의 모든 데이터를 하나씩 비교해야하고, 이후 두 번째 for문에서는 현재 위치 i 다음의 모든 데이터와 비교를 수행하여 중복된 데이터를 찾는다.

중복된 데이터가 발견되면 remove() 메서드를 사용하여 해당 데이터를 제거하고, j 값을 1 감소시켜 다시 검색할 범위를 조정한다. 이렇게 중복된 데이터를 모두 제거한 후에는 반복문을 통해 linked list의 데이터를 출력한다.


특정 데이터 검색 후 인덱스 반환

import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        // LinkedList 객체 생성
        LinkedList<Integer> list = new LinkedList<>();
        
        // 데이터 삽입
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(2);
        list.add(4);
        list.add(1);
        
        // 검색할 데이터
        int target = 3;
        
        // 데이터 검색
        int index = -1;
        for (int i = 0; i < list.size(); i++) {
            if (list.get(i).equals(target)) {
                index = i;
                break;
            }
        }
        
        // 검색 결과 출력
        if (index != -1) {
            System.out.println("찾는 데이터 " + target + "의 인덱스는 " + index + "입니다.");
        } else {
            System.out.println("찾는 데이터 " + target + "가 존재하지 않습니다.");
        }
    }
}

위의 예시 코드에서는 먼저 LinkedList 객체를 생성하고, 여러 개의 데이터를 삽입한다.
이후 검색할 데이터를 변수 target에 저장하고, 반복문을 통해 linked list의 모든 데이터를 검색한다.

검색할 데이터와 현재 데이터가 같으면 해당 인덱스를 변수 index에 저장하고 반복문을 빠져나온다.
검색 결과가 -1이 아닌 경우는 찾는 데이터가 존재하는 경우이고, -1인 경우는 찾는 데이터가 존재하지 않는 것이다. if문을 통해 위 코드처럼 출력할 수 있다.


모든 데이터 역순으로 출력하기

import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        // LinkedList 객체 생성
        LinkedList<Integer> list = new LinkedList<>();
        
        // 데이터 삽입
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(2);
        list.add(4);
        list.add(1);
        
        // 데이터 역순 출력
        for (int i = list.size() - 1; i >= 0; i--) {
            System.out.print(list.get(i) + " ");
        }
    }
}

위의 예시 코드에서는 먼저 LinkedList 객체를 생성하고, 여러 개의 데이터를 삽입한다.
이후 반복문을 통해 linked list의 모든 데이터를 역순으로 출력한다.

반복문에서는 먼저 리스트의 마지막 인덱스를 구한 후,
인덱스를 하나씩 감소시키면서 linked list의 모든 데이터를 역순으로 출력한다.
출력 결과는 1 4 2 3 2 1과 같이 리스트의 역순으로 출력된다.


데이터 오름차순 정렬

import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        // LinkedList 객체 생성
        LinkedList<Integer> list = new LinkedList<>();
        
        // 데이터 삽입
        list.add(5);
        list.add(3);
        list.add(2);
        list.add(4);
        list.add(1);
        
        // 데이터 정렬
        for (int i = 0; i < list.size() - 1; i++) {
            for (int j = 0; j < list.size() - 1 - i; j++) {
                if (list.get(j) > list.get(j + 1)) {
                    int temp = list.get(j);
                    list.set(j, list.get(j + 1));
                    list.set(j + 1, temp);
                }
            }
        }
        
        // 데이터 출력
        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i) + " ");
        }
    }
}

위의 예시 코드에서는 먼저 LinkedList 객체를 생성하고, 여러 개의 데이터를 삽입한다.
이후 <버블 정렬 알고리즘>을 사용하여 linked list의 데이터를 오름차순으로 정렬했다.

버블 정렬 알고리즘은 인접한 두 개의 데이터를 비교하면서 정렬을 수행한다. 따라서 두 개의 반복문을 사용하여 linked list의 모든 데이터를 비교한다. 이후 첫 번째 반복문이 한 번 끝날 때마다 가장 큰 값이 맨 뒤로 이동하므로, 두 번째 반복문의 범위를 하나씩 줄여가면서 반복을 수행한다.

버블 정렬 알고리즘을 사용하여 linked list의 데이터를 정렬한 후, 반복문을 통해 데이터를 출력한다. 출력 결과는 1 2 3 4 5와 같이 오름차순으로 정렬된 데이터가 출력됩니다.


두 개의 LinkedList를 합치기

import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        // LinkedList 객체 생성
        LinkedList<Integer> list1 = new LinkedList<>();
        LinkedList<Integer> list2 = new LinkedList<>();
        
        // 데이터 삽입
        list1.add(1);
        list1.add(2);
        list1.add(3);
        
        list2.add(4);
        list2.add(5);
        list2.add(6);
        
        // 두 개의 LinkedList 합치기
        list1.addAll(list2);
        
        // 합쳐진 데이터 출력
        for (int i = 0; i < list1.size(); i++) {
            System.out.print(list1.get(i) + " ");
        }
    }
}

위의 예시 코드에서는 먼저 두 개의 LinkedList 객체를 생성하고, 각각 데이터를 삽입한다.
이후 addAll() 메서드를 사용하여 list1에 list2를 합친다.
이렇게 합쳐진 데이터를 출력하기 위해서 반복문을 사용한다.

LinkedList 클래스의 addAll() 메서드는 파라미터로 전달된 Collection 객체의 모든 요소를 리스트 끝에 추가한다. 따라서 합치려는 두 리스트가 매우 크거나 요소가 많을 경우에는 성능 이슈가 발생할 수 있으므로, 이러한 경우에는 다른 방법을 고려해야 한다.


LinkedList에서 스택(stack)과 큐(queue) 구현하기

LinkedList를 사용하여 스택과 큐를 구현할 때는 데이터 삽입 및 삭제 시 리스트의 앞과 뒤에서 수행할 수 있는 메소드를 사용하는 것이 중요하다.

  • 스택 stack
import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        // LinkedList 객체 생성
        LinkedList<Integer> stack = new LinkedList<>();
        
        // 데이터 삽입
        stack.addFirst(1);
        stack.addFirst(2);
        stack.addFirst(3);
        
        // 데이터 출력
        while (!stack.isEmpty()) {
            System.out.print(stack.removeFirst() + " ");
        }
    }
}

스택은 맨 위에 있는 데이터를 먼저 꺼내는 구조이므로, LinkedList의 addFirst()와 removeFirst() 메서드를 사용하여 스택을 구현할 수 있다. addFirst() 메소드는 리스트의 맨 앞에 데이터를 추가하고, removeFirst() 메소드는 리스트의 맨 앞에서 데이터를 삭제한다.

위의 예시 코드에서는 먼저 LinkedList 객체를 생성하고, addFirst() 메소드를 사용하여 데이터를 삽입한다. 이후 removeFirst() 메소드를 사용하여 스택의 데이터를 꺼내어 출력한다.

:)

  • 큐 queue
import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        // LinkedList 객체 생성
        LinkedList<Integer> queue = new LinkedList<>();
        
        // 데이터 삽입
        queue.addLast(1);
        queue.addLast(2);
        queue.addLast(3);
        
        // 데이터 출력
        while (!queue.isEmpty()) {
            System.out.print(queue.removeFirst() + " ");
        }
    }
}

큐는 맨 앞에 있는 데이터를 먼저 꺼내는 구조이므로, LinkedList의 addLast()와 removeFirst() 메소드를 사용하여 큐를 구현할 수 있다. addLast() 메소드는 리스트의 맨 뒤에 데이터를 추가하고, removeFirst() 메소드는 리스트의 맨 앞에서 데이터를 삭제한다.

위의 예시 코드에서는 먼저 LinkedList 객체를 생성하고, addLast() 메소드를 사용하여 데이터를 삽입한다. 이후 removeFirst() 메소드를 사용하여 큐의 데이터를 꺼내어 출력한다.



LinkedList의 메소드

1. offer() 메소드

리스트의 맨 뒤에 데이터를 추가한다. 만약 리스트가 가득 차 있으면 false를 반환한다.
아래 예시 코드에서는 LinkedList 객체를 생성하고, offer() 메소드를 사용하여 데이터를 추가한다.
이렇게 추가된 데이터를 출력하기 위해서는 리스트 객체를 직접 출력하면 된다.

import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        // LinkedList 객체 생성
        LinkedList<Integer> list = new LinkedList<>();
        
        // 데이터 추가
        list.offer(1);
        list.offer(2);
        list.offer(3);
        
        // 데이터 출력
        System.out.println(list);
    }
}

2. poll() 메소드

리스트의 맨 앞에서 데이터를 삭제하고 반환한다. 만약 리스트가 비어 있으면 null을 반환한다.
아래 예시 코드에서는 LinkedList 객체를 생성하고, add() 메소드를 사용하여 데이터를 추가한다.
이후 poll() 메소드를 사용하여 데이터를 삭제하고, 삭제된 데이터를 출력한다.

import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        // LinkedList 객체 생성
        LinkedList<String> list = new LinkedList<>();
        
        // 데이터 추가
        list.add("apple");
        list.add("banana");
        list.add("cherry");
        
        // 데이터 삭제
        while (!list.isEmpty()) {
            String data = list.poll();
            System.out.println("poll: " + data);
        }
    }
}

3. peek() 메소드

리스트의 맨 앞에 있는 데이터를 반환합니다. 리스트가 비어 있으면 null을 반환한다.
아래 예시 코드에서는 LinkedList 객체를 생성하고, offer() 메소드를 사용하여 데이터를 추가한다.
이후 peek() 메소드를 사용하여 맨 앞에 있는 데이터를 출력한다.

import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        // LinkedList 객체 생성
        LinkedList<Integer> list = new LinkedList<>();
        
        // 데이터 추가
        list.offer(1);
        list.offer(2);
        list.offer(3);
        
        // 데이터 출력
        System.out.println(list.peek());
    }
}

4. peekLast() 메소드

리스트의 맨 앞에 있는 데이터를 반환한다. 리스트가 비어 있으면 null을 반환한다.
아래 예시 코드에서는 LinkedList 객체를 생성하고, offer() 메소드를 사용하여 데이터를 추가한다.
이후 peekLast() 메소드를 사용하여 맨 뒤에 있는 데이터를 출력합니다.

import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        // LinkedList 객체 생성
        LinkedList<Integer> list = new LinkedList<>();
        
        // 데이터 추가
        list.offer(1);
        list.offer(2);
        list.offer(3);
        
        // 데이터 출력
        System.out.println(list.peek());
    }
}

🌌 Chat-GPT 예제소스

1. 원형 이중 연결 리스트 만들기

이중 연결 리스트는 단일 연결 리스트와 유사하지만, 각 노드가 다음 노드뿐만 아니라 이전 노드를 가리키는 포인터도 가지고 있다는 차이점이 있다. 그리고 원형 연결 리스트는 마지막 노드가 첫 번째 노드를 가리키는 것으로서, 원형 구조를 갖는다.

public class CircularDoublyLinkedList {
    // 이중 연결 리스트의 노드 클래스 정의
    private static class Node {
        int data; // 노드의 데이터
        Node prev; // 이전 노드를 가리키는 포인터
        Node next; // 다음 노드를 가리키는 포인터
    }

    // 원형 이중 연결 리스트 클래스의 필드 정의
    private Node head; // 리스트의 첫 번째 노드를 가리키는 포인터

    // 원형 이중 연결 리스트의 생성자
    public CircularDoublyLinkedList() {
        head = null; // 첫 번째 노드가 없으므로 null로 초기화
    }

    // 새로운 노드를 리스트에 추가하는 메서드
    public void addNode(int data) {
        Node newNode = new Node(); // 새로운 노드 생성
        newNode.data = data; // 새로운 노드의 데이터 설정

        if (head == null) {
            // 리스트가 비어있을 경우, 새로운 노드가 리스트의 첫 번째 노드가 됨
            head = newNode;
            head.prev = head; // 첫 번째 노드의 이전 노드는 자기 자신을 가리킴
            head.next = head; // 첫 번째 노드의 다음 노드는 자기 자신을 가리킴
        } else {
            // 리스트가 비어있지 않을 경우, 마지막 노드의 다음 노드로 새로운 노드를 추가
            Node tail = head.prev; // 마지막 노드를 찾기 위해 head의 이전 노드부터 시작
            tail.next = newNode; // 마지막 노드의 다음 노드를 새로운 노드로 설정
            newNode.prev = tail; // 새로운 노드의 이전 노드를 마지막 노드로 설정
            newNode.next = head; // 새로운 노드의 다음 노드를 첫 번째 노드로 설정
            head.prev = newNode; // 첫 번째 노드의 이전 노드를 새로운 노드로 설정
        }
    }

    // 리스트의 모든 노드를 출력하는 메서드
    public void printList() {
        if (head == null) {
            // 리스트가 비어있을 경우, "리스트가 비어있습니다." 메시지 출력
            System.out.println("리스트가 비어있습니다.");
            return;
        }

        Node curr = head; // 현재 노드를 가리키는 포인터 초기화
        do {
            // do-while 문을 사용하여 리스트의 모든 노드 출력
            System.out.print(curr.data + " "); // 현재 노드의 데이터 출력
            curr = curr.next; // 현재 노드의 다음 노드를 현재 노드로 설정
        } while (curr != head); // curr이 head를 가리킬 때까지 반복
    }


    public static void main(String[] args) {
        CircularDoublyLinkedList list = new CircularDoublyLinkedList();
        // 원형 이중 연결 리스트 인스턴스 생성

        list.addNode(4); // 리스트에 노드 추가
        list.addNode(5); // 리스트에 노드 추가
        list.addNode(6); // 리스트에 노드 추가

        list.printList(); // 리스트 출력
    }
}

2. 두 개의 연결 리스트 교차 지점 찾기

이 문제는 LinkedList의 개념과 포인터를 이용한 탐색 알고리즘을 이해하고 있어야 한다.
이 코드는 시간 복잡도 O(N+M)과 공간 복잡도 O(1)을 가진다.
NM은 각각 두 LinkedList의 길이를 나타낸다.

class ListNode {
    int val;
    ListNode next;

    // ListNode 생성자
    ListNode(int x) {
        val = x;
        next = null;
    }
}

public class Solution {
    /**
     * 두 LinkedList의 교차 지점을 찾는 메서드
     *
     * @param headA 첫 번째 LinkedList의 헤드 노드
     * @param headB 두 번째 LinkedList의 헤드 노드
     * @return 두 LinkedList의 교차 지점, 교차 지점이 없을 경우 null 반환
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 하나 이상의 LinkedList가 비어있는 경우, 교차 지점이 없으므로 null 반환
        if (headA == null || headB == null) {
            return null;
        }

        // 두 포인터 생성
        ListNode currA = headA;
        ListNode currB = headB;

        // 두 포인터가 교차 지점에서 만날 때까지 반복
        while (currA != currB) {
            // currA가 끝에 도달하면 headB로 이동
            currA = (currA == null) ? headB : currA.next;

            // currB가 끝에 도달하면 headA로 이동
            currB = (currB == null) ? headA : currB.next;
        }

        // 교차 지점 반환
        return currA;
    }

        public static void main(String[] args) {
            ListNode node1 = new ListNode(1);
            ListNode node2 = new ListNode(2);
            ListNode node3 = new ListNode(3);

            node1.next = node2;
            node2.next = node3;

            ListNode node4 = new ListNode(4);
            ListNode node5 = new ListNode(5);

            node4.next = node5;
            node5.next = node2;

            Solution solution = new Solution();
            ListNode intersectionNode = solution.getIntersectionNode(node1, node4);

            if (intersectionNode == null) {
                System.out.println("두 LinkedList는 교차하지 않습니다.");
            } else {
                System.out.println("교차 지점의 값: " + intersectionNode.val);
            }
        }
    }

위 코드에서는 ListNode 클래스는 LinkedList의 노드를 나타내는 클래스다.
ListNode 클래스에는 val 필드와 next 포인터가 있다.
Solution 클래스는 두 LinkedList의 교차 지점을 찾는 클래스이다.

아래는 단계별 설명 🔥

getIntersectionNode() 메소드는 두 개의 매개변수 headA(첫번째 헤드 노드)와 headB(두번째 헤드 노드)를 받아서, 두 LinkedList의 교차 지점을 찾는 메소드다.

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

먼저, 하나 이상의 LinkedList가 비어있는 경우, 교차 지점이 없으므로 null을 반환한다

// 하나 이상의 LinkedList가 비어있는 경우, 교차 지점이 없으므로 null 반환
if (headA == null || headB == null) {
    return null;
}

그리고 currAcurrB 두 포인터를 생성하고, 반복문 안에서는 먼저 currAnull인 경우, headB로 이동한다. 이 때, 삼항 연산자를 이용하여 간단하게 작성할 수 있다.

// currA가 끝에 도달하면 headB로 이동
currA = (currA == null) ? headB : currA.next;

그리고 currBnull인 경우, headA로 이동한다.

// currB가 끝에 도달하면 headA로 이동
currB = (currB == null) ? headA : currB.next;

두 포인터가 교차 지점에서 만나면 그 위치를 반환한다.

// 교차 지점 반환
return currA;

위 코드에서는 두 포인터가 교차 지점에서 만날 때까지 반복하므로, 두 LinkedList의 길이가 같아도 교차 지점이 없는 경우에는 반드시 null을 반환한다.


profile
I'm still hungry.

0개의 댓글