给定一个单链表的头结点pHead(该头节点是有值的,比如在下图,它的val是1),长度为n,反转该链表后,返回新链表的表头。
数据范围:
要求:空间复杂度 ,时间复杂度 。
如当输入链表{1,2,3}时,
经反转后,原链表变为{3,2,1},所以对应的输出为{3,2,1}。
以上转换过程如下图所示:
{1,2,3}
{3,2,1}
{}
{}
空链表则输出空
public ListNode ReverseList (ListNode head) { if(head == null) return null;//如果给的是空链表,直接返回空 if(head.next == null) return head;//如果给的链表只有一个节点,不用反转,直接返回 //如果链表至少是两个节点,才执行下面的代码 ListNode temp = head.next;//要反转的节点(从第二个节点开始) ListNode nextNode = temp.next;//要反转的节点的下一个节点 head.next = null;//先断开头节点和要反转节点的连接,不然反转完之后会形成环 //头插法进行反转 while (temp != null){ temp.next = head; head = temp; temp =nextNode; if(nextNode != null) nextNode = nextNode.next; } return head; }时间复杂度O(n) 空间复杂度O(1)。
import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * public ListNode(int val) { * this.val = val; * } * } */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param head ListNode类 * @return ListNode类 */ public ListNode ReverseList (ListNode head) { if(head==null) return null; ListNode newList = null; while(head!=null){ ListNode temp = head.next; //临时存储 head.next=newList; //改箭头 newList=head; //指针后移更新新表 head=temp; //指针后移更新旧表 } return newList; } }
import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * public ListNode(int val) { * this.val = val; * } * } */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param head ListNode类 * @return ListNode类 */ public ListNode ReverseList (ListNode head) { // write code here ListNode prev = null;//当前节点的上一个节点 ListNode curr = head;//当前的节点 while(curr!=null){ ListNode nextTemp = curr.next;//临时保存当前节点的下个节点 curr.next = prev;//当前节点指向上一个节点 prev = curr;//上一个节点设置成当前节点 curr = nextTemp;//当前节点设置为下个节点 } return prev; } }
public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param head ListNode类 * @return ListNode类 */ // 思路:用新头结点替换原头节点,并将原头节点后移一位,然后再次循环替换、移位,直至原头结点为空,最后返回新的头节点 public ListNode ReverseList (ListNode head) { // write code here //创建新的头节点 ListNode newHead = null; // 头节点不为空时进行循环 while(head!=null){ // 将头结点的下一个节点赋值给临时节点 ListNode temp = head.next; // 头节点指向新的头节点 head.next = newHead; // 头结点赋值给新的头节点 newHead = head; // 临时节点赋值给头结点,完成头结点后移 head = temp; } // 返回新的头节点 return newHead; } }
import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * public ListNode(int val) { * this.val = val; * } * } */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param head ListNode类 * @return ListNode类 */ public ListNode ReverseList (ListNode head) { // write code here //res用于保存最终结果 // ListNode res=null; // ListNode tail=res; // ListNode p=head; // while(p!=null){ // ListNode tmp=p.next; // p.next=tail; // tail=p; // p=tmp; // } // return tail; //栈 Stack<ListNode>s=new Stack<>(); ListNode p=head; while(p!=null){ s.push(p); p=p.next; } ListNode res=new ListNode(-1); ListNode tail=res; while(!s.isEmpty()){ ListNode node=s.pop(); tail.next=node; node.next=null; tail=node; } tail.next=null; return res.next; } }
import java.util.*; class ListNode { int val; ListNode next; ListNode(int val) { this.val = val; } } public class Solution { public ListNode ReverseList(ListNode head) { Stack<ListNode> stack = new Stack<>(); ListNode tempNode = head; while (tempNode != null) { stack.push(tempNode); tempNode = tempNode.next; } if (stack.isEmpty()) { return null; } ListNode node = stack.pop(); ListNode reversedNode = node; while (!stack.isEmpty()) { ListNode temNode = stack.pop(); node.next = temNode; node = node.next; } node.next = null; return reversedNode; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); if (scanner.hasNext()) { String inputLine = scanner.nextLine().trim(); ListNode reversedNode; Solution solution = new Solution(); if("{}".equals(inputLine)){ reversedNode = solution.ReverseList(null); }else{ String[] valueArray = inputLine.substring(1, inputLine.length()-1).split(","); if(valueArray.length==1){ reversedNode = new ListNode(Integer.parseInt(valueArray[0])); }else if(valueArray.length==2){ reversedNode = new ListNode(Integer.parseInt(valueArray[1])); reversedNode.next = new ListNode(Integer.parseInt(valueArray[0])); } else{ ListNode firstNode = new ListNode(Integer.parseInt(valueArray[0])); ListNode secondNode = new ListNode(Integer.parseInt(valueArray[1])); firstNode.next = secondNode; for(int i=2;i<valueArray.length-1;i++){ ListNode temNode = new ListNode(Integer.parseInt(valueArray[i])); secondNode.next = temNode; secondNode = secondNode.next; } ListNode endNode = new ListNode(Integer.parseInt(valueArray[valueArray.length-1])); secondNode.next = endNode; endNode.next = null; reversedNode = solution.ReverseList(firstNode); } } solution.printList(reversedNode); } } public void printList(ListNode head) { if (head == null) { System.out.println("{}"); return; } StringBuilder builder = new StringBuilder(); builder.append("{"); ListNode curr = head; while (curr != null) { if (curr.next != null) { builder.append(curr.val).append(","); } else { builder.append(curr.val); } curr = curr.next; } builder.append("}"); System.out.print(builder); } }
public ListNode ReverseList (ListNode head) { // write code here // 递归法 // if(head==null || head.next==null) return head; // ListNode next=ReverseList(head.next); // head.next.next=head; // head.next=null; // return next; //遍历法 if(head==null) return head; ListNode prev=null; while(head!=null){ ListNode next=head.next; head.next=prev; prev=head; head=next; } return prev; }
public ListNode ReverseList (ListNode head) { // write code here if(head == null){ return null; } ListNode listNode = new ListNode(head.val); while(head.next != null){ head = head.next; ListNode list = new ListNode(head.val); list.next = listNode; listNode = list; } return listNode; }
public ListNode ReverseList (ListNode head) { // write code here //首节点 ListNode y=head; if(y!=null) { //首节点的后继 ListNode t=y.next; //保存点 ListNode b=y.next; //首节点变尾节点 head.next=null; while(b!=null){ //预先获取下一个节点 b=b.next; //反转 t.next=y; //待链接节点遍历 y=t; //反转节点遍历 t=b; } } return y; }