[데이터 구조 - 9] 두 결점 헤드 가 있 는 비공 식 단일 체인 테이블 을 지정 하고 체인 테이블 의 중간 결점 을 되 돌려 줍 니 다

2698 단어 데이터 구조
제목 설명:
머리 결점 헤드 가 있 는 비공 식 단일 체인 시 계 를 정 하고 체인 시계의 중간 결점 을 되 돌려 줍 니 다. 만약 에 두 개의 중간 결점 이 있 으 면 두 번 째 중간 결점 으로 돌아 갑 니 다.
예시 1:
입력: [1, 2, 3, 4, 5] 출력: 이 목록 의 노드 3 (직렬 화 형식: [3, 4, 5]) 에서 돌아 오 는 노드 값 은 3 입 니 다.
예시 2:
입력: [1, 2, 3, 4, 5, 6] 출력: 이 목록 의 결점 4 (서열 화 형식: [4, 5, 6]) 이 목록 은 두 개의 중간 결점 이 있 기 때문에 값 은 각각 3 과 4 이다. 우 리 는 두 번 째 결점 으로 돌아간다.
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

사고 분석:
1. 빠 르 고 느 린 지침 을 만들어 서 같이 가게 합 니 다. 그러나 하 나 는 두 걸음 을 걷 고 하 나 는 한 걸음 을 걷 습 니 다. 2. 빠 른 지침 이 NULL 에 갔 을 때 노드 가 홀수 일 때 느 린 지침 은 바로 중간 노드 이 고 노드 가 짝수 일 때 느 린 지침 은 바로 두 중간 노드 중의 두 번 째 3 입 니 다. 주의: 1. , pCur!=NULL, , pCur->next!=NULL 2. , &&코드 구현:
struct ListNode* middleNode(struct ListNode* head)
{
    struct ListNode* pCur=head;
    struct ListNode* pPre=head;
    while(pCur!=NULL && pCur->next!=NULL)
    {
        pCur=pCur->next->next;
        pPre=pPre->next;
    }
    return pPre;
}

좋은 웹페이지 즐겨찾기