反转链表，不能用辅助数据结构

反转链表

1.不能用辅助数据结构，不能用递归，链表自己定义 next int

代码语言：javascript复制

//单向链表节点
public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

/**
* 反转链表的方法
* @param head 链表的头节点
* @return ListNode 一个反转后的头结点
*/
public ListNode reverseList(ListNode head) {
    ListNode cur = head;
    ListNode pre = null;
    while(cur!=null){
    	//保存当前节点下一个节点
        ListNode temp = cur.next;
        //指向前一个节点（头结点指向null）
        cur.next = pre;
        pre = cur;
        cur = temp;
    }
    //将反转后的链表头节点返回
    return pre;
}

2.我写的垃圾代码

代码语言：javascript复制

//类似冒泡，将第一个val一直冒泡到最后一位，以此类推
private static ListNode turnList(ListNode input) {
	if(input == null) {
		return null;
	}
	ListNode node = input;
	ListNode now = input;
	
	//获取链表长度
	int length =0;

	while(node!=null) {
		length  ;
		node = node.next;
	}

	
	for(int i = 0;i<length;i  ) {
		node = input;
		System.out.println("exchange time:" (length-i));
		//int val = node.value;
		//这个地方用到了i，用i来控制要交换多少次，第一个要交换length-1次，第二个要交换length-2，第n个交换length-n
		for(int j = 0;j<length-i-1;j  ) {
			
			if(node.next == null) {
				break;
			}
			exchange(node,node.next);
			PrintList(input);
			node = node.next;
		}
		now = now.next;
	}

	return input;
}

private static void exchange(ListNode node, ListNode next) {
	int val = node.value;
	node.value = next.value;
	next.value = val;		
}

编程

0 人点赞