링크 기초 계산법 문제
37119 단어 데이터 구조 와 알고리즘데이터 구조체인 테이블
반전 링크: 링크 의 머리 노드 를 입력 하고 이 링크 를 반전 시 키 며 반전 후 링크 의 머리 노드 를 출력 합 니 다.
링크 가 1 → 2 → 3 → 8709 이 고 반전 후 에는 8709 이 며 ← 1 ← 2 ← 3 이다.링크 를 옮 겨 다 닐 때 현재 노드 의 next 지침 을 이전 노드 로 바 꿉 니 다.노드 가 이전 노드 를 인용 하지 않 았 기 때문에 이전 노드 를 미리 저장 해 야 합 니 다.인용 을 변경 하기 전에 다음 노드 를 저장 해 야 합 니 다.마지막 으로 새로운 헤더 인용 을 되 돌려 줍 니 다.
public ListNode reverseList(ListNode head) {
ListNode pre=null;
ListNode curr=head;
while (curr!=null){
ListNode next=curr.next;
curr.next=pre;//
pre=curr;//
curr=next;
}
return pre;
}
2. 정렬 된 링크 두 개 를 합 칩 니 다.
NowCoder
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1 == null && l2 == null) return null;
ListNode head=new ListNode(-1);
ListNode temp=head;
while (l1!=null && l2 !=null){
if(l1.val > l2.val){
temp.next=l2;
l2=l2.next;
}else {
temp.next=l1;
l1=l1.next;
}
temp=temp.next;
}
temp.next= l1==null? l2:l1;
return head.next;
}
3. 링크 노드 삭제
https://leetcode-cn.com/problems/shan-chu-lian-biao-de-jie-dian-lcof/
public ListNode deleteNode(ListNode head, int val) {
if(head == null) return null;
if(head.val==val) return head.next;
//
ListNode pre=head;
ListNode cur=head.next;
//
while (cur.val != val){
pre=pre.next;
cur=cur.next;
}
pre.next = cur.next;
return head;
}
4. 링크 에서 중복 되 는 노드 삭제 (포인트)
NowCoder
public ListNode deleteDuplication(ListNode pHead){
if(pHead == null || pHead.next == null) return pHead;
//
ListNode head = new ListNode(Integer.MIN_VALUE);
head.next = pHead;
ListNode pre = head;
ListNode cur = head.next;
while(cur!=null){
if(cur.next != null && cur.next.val == cur.val){
//
while(cur.next != null && cur.next.val == cur.val)
cur = cur.next;
// ，cur ， ， cur.next
cur = cur.next;
// pre
pre.next = cur;
}else{
pre = cur;
cur = cur.next;
}
}
return head.next;
}
5. 빠 르 고 느 린 지침 문제 (중점)
1. 링크 의 중간 노드
링크 의 중간 노드
2. 링크 중앙 고리 의 입구 노드
NowCoder
두 개의 바늘 을 사용 합 니 다. 빠 른 바늘 fast 는 매번 두 개의 노드 를 이동 하고 느 린 바늘 slow 는 매번 한 노드 를 이동 합 니 다.고리 가 존재 하기 때문에 두 바늘 은 반드시 고리 의 한 노드 에서 만 날 것 이다.링 리스트 의 중간 고리 가 있 는 입구 결점 을 찾 습 니 다.빠 르 고 느 린 지침 이 만 났 을 때 우 리 는 링크 에 고리 가 있다 는 것 을 판단 할 수 있다. 이때 새로운 지침 이 링크 의 출발점 을 가리 키 고 걸음 길이 가 느 린 지침 과 같 으 면 느 린 지침 이 '새로운' 지침 과 만 나 는 곳 이 바로 링 의 입구 이다.
public ListNode detectCycle(ListNode head) {
if(head == null) return null;
ListNode slow=head;
ListNode fast=head;
boolean flag=false;
while (fast!=null && fast.next!=null){
fast=fast.next.next;
slow=slow.next;
if(fast == slow){
flag=true;
break;
}
}
if(!flag) return null;// null
//
ListNode cur=head;
while (cur!=slow){
cur=cur.next;
slow=slow.next;
}
return cur;
}
3. 링크 의 마지막 K 번 째 노드
https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/
링크 의 길 이 를 N 으로 설정 합 니 다.두 개의 포인터 fast 와 slow 를 설정 하고 fast 가 K 개의 노드 를 먼저 이동 시 키 면 N - K 개의 노드 가 이동 할 수 있 습 니 다.이때 fast 와 slow 를 동시에 이동 시 키 면 fast 가 링크 의 끝 에 이동 할 때 slow 는 N - K 개 노드 로 이동 하고 이 위 치 는 꼴찌 K 개 노드 임 을 알 수 있다.
public ListNode getKthFromEnd(ListNode head, int k) {
if(head == null) return null;
ListNode slow=head;
ListNode fast=head;
for (int i = 0; i < k; i++)
fast=fast.next;
while (fast !=null){
fast=fast.next;
slow=slow.next;
}
return slow;
}
4. 리 턴 링크
버클 주소: 링크 가 답장 구조 인지 판단 합 니 다.
방법 1: 스 택 을 통 해 모든 숫자 를 눌 러 넣 고 한 번 더 옮 겨 다 니 며 순서대로 비교 합 니 다.
방법 2: 빠 르 고 느 린 포인터 + 반전 링크.빠 르 고 느 린 지침 을 통 해 먼저 느 린 지침 을 중심 점 까지 가게 한 다음 에 남 은 부분 을 반전 시킨다.반전 이 끝 난 후에 변 수 를 정의 합 니 다.
public boolean isPalindrome(ListNode head) {
if(head == null) return false;
if(head.next==null) return true;
ListNode slow=head;
ListNode fast=head;
while(fast!=null && fast.next!=null){
slow=slow.next;
fast=fast.next.next;
}
// ，slow
ListNode pre=null;
ListNode cur=slow;
while(cur!=null){
ListNode next=cur.next;
cur.next=pre;
pre=cur;
cur=next;
}
// pre 1->2 2
ListNode p2=pre;
ListNode p1=head;
while(p2!=null){
if(p1.val != p2.val) return false;// false
p1=p1.next;
p2=p2.next;
}
return true;
}
5. 교차 링크
교차 링크: 두 개의 단일 링크 가 교차 하 는 시작 노드 를 찾 습 니 다.
사상: 먼저 두 개의 링크 의 길 이 를 통계 한 다음 에 서로 줄 이 는 것 이 바로 그들의 걸음 차이 이다. 그 다음 에 긴 것 이 먼저 걸음 차이 의 길 이 를 걷 게 한 다음 에 두 개의 링크 가 함께 이동 하고 교차 하 는 것 은 교차 노드 이다.
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA == null || headB==null) return null;
ListNode l1=headA;
ListNode l2=headB;
int countA=0,countB=0;
while(l1!=null){
countA++;
l1=l1.next;
}
while(l2!=null){
countB++;
l2=l2.next;
}
ListNode a=headA;
ListNode b=headB;
int skip=Math.abs(countA-countB);
if(countA>countB)
while(skip>0) {
a=a.next;
skip--;
}
else if(countA<countB)
while(skip>0) {
b=b.next;
skip--;
}
while(a!=null && b!=null){
if(a==b) return a;
a=a.next;
b=b.next;
}
return null;
}
6. 회전 우 이동 링크
버클 주소
사고방식: 먼저 몇 개의 숫자 가 있 는 지 통계 한 다음 에 몇 개의 위 치 를 이동 해 야 하 는 지 판단 하고 그 를 순환 체인 테이블 로 만 든 다음 에 지 정 된 보폭 을 이동 한 다음 에 순환 을 깨 뜨 린 다
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if(head==null)
return null;
else {
ListNode node=head;
ListNode listNode=new ListNode(0);
int count=0;//
while (node.next!=null){
node=node.next;
count++;
}
count++;
int flag=count - k % count+1;//
node.next=head;//
ListNode temp=head;
for (int i = 1; i < flag; i++)
temp=temp.next;
listNode.next=temp;//
//
ListNode cur=listNode;
for (int i = 0; i < count; i++)
cur=cur.next;
cur.next=null;
return listNode.next;
}
}
}
7. 분리 링크
단 방향 링크 를 특정한 값 에 따라 왼쪽 이 작고 중간 이 같 으 며 오른쪽 이 큰 형식 으로 나 누 었 다.
사고: 6 개의 빈 링크 지침 을 정의 하고 각각 왼쪽, 오른쪽 으로 나 눈 다음 에 크기 를 비교 하여 해당 하 는 링크 위치 에 놓 고 최종 적 으로 연결 하면 됩 니 다.
이것 은 간단 한 분리 링크 이다. 링크 를 구분 하여 모든 작은 노드 가 4. 567914 보다 크 거나 4. 567914 와 같은 노드 앞 에 나타난다.
public ListNode partition(ListNode head, int x) {
if(head == null) return null;
ListNode left=new ListNode(-1);
ListNode lp=left;
ListNode right=new ListNode(-1);
ListNode rp=right;
while(head!=null){
if(head.val < x){
lp.next=head;
lp=lp.next;
}else {
rp.next=head;
rp=rp.next;
}
head=head.next;
}
rp.next=null;// null
// ，
if(left.next == null) return right.next;//
if(right.next == null) return left.next;//
lp.next=right.next;//
return left.next;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[JAVA] 배열 회전 출력요소 가 출력 을 시작 하 는 위치 에 주의 하 십시오. 모두 몇 라운드 의 수출 이 있 습 니까? n/2 + 1 매 라 운 드 는 상, 우, 하, 좌 로 나 뉜 다. 각 방향의 시작 위치 와 좌표 의 관 계 를 구...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
