19.Reverse Linked List

1930 단어
Reverse a singly linked list.
click to show more hints.
Hint:
A linked list can be reversed either iteratively or recursively. Could you implement both?
분석: 제목 요구는 체인 테이블의 전환을 실현하는 것이다.
세 가지 구현:
1. 귀속
/* */
	 public ListNode reverseList(ListNode head) {
		 if(head == null){
			 return null;
		 }
		 ListNode p = head;
		 if(head.next == null){
			 return head;
		 }else{	
			 ListNode list = reverseList(head.next);
			 p.next.next = p;
			 p.next = null;/* p null*/
			 return list;
		}
	  }

2. 교체
l1은 이미 역순으로 배열된 두결점을 나타낸다.
l2는 뒤에 체인을 거꾸로 배열해야 하는 두결점을 나타낸다
l3=l2.next
 /* */
	 public ListNode reverseList2(ListNode head) {
		 if(head == null || head.next == null){
			 return head;
		 }else{
			 ListNode l1 = head;
			 ListNode l2 = l1.next;
			 l1.next = null;/* null*/
			 
			 while(l2.next != null){
				 ListNode l3 = l2.next;
				 l2.next = l1;
				 l1 = l2;
				 l2 =l3;
			 }			 
			 l2.next = l1;
			 return l2;			 
		 }
	    }
public ListNode ReverseList2(ListNode head) {
		 if(head == null){
			 return head;
		 }else{
			 ListNode l1 = null;
			 ListNode l2 = head;
			 
			 while(l2.next != null){
				 ListNode l3 = l2.next;
				 l2.next = l1;
				 l1 = l2;
				 l2 =l3;
			 }			 
			 l2.next = l1;
			 return l2;			 
		 }
   }

3. 모든 값을 훑어본 다음에 체인 테이블의 노드에 다시 값을 부여한다.
 <span style="white-space:pre">	</span>/**
	  *  ,  
	  */
	 public ListNode reverseList3(ListNode head) {
		 ListNode p = head;
		 ArrayList vallist = new ArrayList<Integer>();
		 while(p!=null){
			 vallist.add(p.val);
			 p = p.next;
		 }
		 p = head;
		 for(int i=vallist.size()-1;i>=0;i--){
			 p.val = (int) vallist.get(i);
			 p =p.next;
		 }
		 
		 return head;
	    }

체인 시계의 제목은 순환의 끝 조건을 중점적으로 제어해야 한다.

좋은 웹페이지 즐겨찾기