투 포인터 - Middle of the Linked List

2022. 1. 12. 20:55

https://blog.naver.com/nagne2011/222620076723

3. 투 포인터 - Middle of the Linked List

 

 

#twopointer #알고리즘

대표사진 삭제

사진 설명을 입력하세요.

Linked List에서 모든 노드의 중앙값을 구하는 알고리즘

 

링크드 리스트는 그다지 많이 다루지 않아서 엄청 헤매다가 결국 강좌를 봤다

 

의외로 방법은 간단했는데 두개의 노드 포인터를 두고

하나는 1칸씩, 다른 하나는 2칸씩 노드를 진행시키는 방식이다

 

그림으로 보면 더 간단하다

사진 삭제

https://dev.to/alisabaj/finding-the-middle-of-a-linked-list-36kp

그 다음 두칸씩 진행되는 노드 포인터가 끝이날때(= 마지막 노드일때)

한칸씩 진행되는 노드 포인트를 리턴하면된다

 

코드로 쓰면 이런느낌

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode MiddleNode(ListNode head) {
        
        ListNode slowNode = head;
        ListNode fastNode = head;
        
        while(fastNode != null 
             && fastNode.next != null)
        {
            slowNode = slowNode.next;
            fastNode = fastNode.next.next;
        }
        
        return slowNode;
    }
}

 

---

심화 문제도 풀어보자

대표사진 삭제

사진 설명을 입력하세요.

입력한 값(n)만큼 뒤에서 n번째 데이터를 삭제하는 문제

 

이전 코드처럼 각 노드의 next들을 이용하여 구분한다

 

 

처음엔 이해가 안되서 한참 들여다봤는데 노드 갯수를 늘려보니 이해가 조금 쉬웠다

대표사진 삭제

사진 설명을 입력하세요.

코드와 같이 비교해서 보자

public class Solution {
    public ListNode RemoveNthFromEnd(ListNode head, int n) {
        
        ListNode slowNode = head;
        ListNode fastNode = head;
        
        for(int i=0; i<n; i++)
        {
            fastNode = fastNode.next;
        }
        
        if(fastNode == null) return head.next;
        
        while(fastNode != null 
             && fastNode.next != null)
        {
            slowNode = slowNode.next;
            fastNode = fastNode.next;
        }
        
        slowNode.next = slowNode.next.next;
        return head;
    }
}

 

일단 두개의 노드 시작점을 잡고

먼저 빠른노드(fastNode)가 먼저 출발한다

빠른노드는 n번만큼 next노드로 진행한다

대표사진 삭제

사진 설명을 입력하세요.

그럼 fastNode는 3번으로 이동하는데,

이제 여기서 fastNode와 slowNode를 같이 출발시킨다

 

그리고 fastNode가 노드 끝에 도착했을때 멈추게되면 (5회 반복)

대표사진 삭제

사진 설명을 입력하세요.

slowNode는 fastNode가 n칸 앞서간 만큼 뒤로 밀려서 멈추게된다

즉, fastNode가 8번으로 이동해서 while문이 멈췄을때 slowNode는 6번에서 멈춘다

그다음 slowNode.next에 slowNode.next.next를 대입해서 (6->7을 6->8로)

노드 하나를 노드목록에서 삭제하면

뒤에서 2번째 노드인 7번이 삭제가 된다